Skip to main content

qualia_core_db/sparql_library/
range_join_select.rs

1//! Range-native nested-loop joins wrapped by Project / Filter / Limit.
2//!
3//! The existing join kernel only accepted a root `NestedLoopJoin`. Real SELECT
4//! trees are `Project(Filter(Limit(Join(Scan, Scan))))`. This module peels those
5//! wrappers without materialising a resident graph.
6
7use super::range_select_apply::{apply_select_wrappers, SelectWrapperState};
8use super::sparql_ast::{BindingRow, SparqlQueryContext, VariableId, MAX_VARIABLES};
9use super::sparql_executor::{
10    execute_range_nested_loop_join_page_into, execute_range_volume_set_nested_loop_join_page_into,
11    Q42RangeNestedLoopJoinPage, Q42RangeNestedLoopJoinPlan, Q42RangeNestedLoopJoinState,
12    Q42RangeVolumeSetNestedLoopJoinState,
13};
14use super::sparql_planner::{ExecutionPlan, PhysicalOperatorType};
15use crate::NQuin;
16
17/// A join plus the SELECT wrappers that sit above it.
18#[derive(Clone, Copy, Debug, Eq, PartialEq)]
19pub struct Q42RangeJoinSelectPlan {
20    pub join: Q42RangeNestedLoopJoinPlan,
21    pub projection: [VariableId; MAX_VARIABLES],
22    pub projection_count: u8,
23    pub filters: [super::sparql_ast::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 Q42RangeJoinSelectState {
31    pub join: Q42RangeNestedLoopJoinState,
32    pub wrappers: SelectWrapperState,
33}
34
35#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
36pub struct Q42RangeVolumeSetJoinSelectState {
37    pub join: Q42RangeVolumeSetNestedLoopJoinState,
38    pub wrappers: SelectWrapperState,
39}
40
41impl Q42RangeJoinSelectPlan {
42    /// Builds `Q42RangeJoinSelectPlan` from `execution_plan`.
43    pub fn from_execution_plan(plan: &ExecutionPlan) -> Result<Self, String> {
44        if plan.operator_count == 0 || plan.root_operator as usize >= plan.operator_count as usize {
45            return Err("range join-select requires a non-empty execution plan".to_string());
46        }
47        let mut operator = plan.root_operator;
48        let mut projection = [0; MAX_VARIABLES];
49        let mut projection_count = 0;
50        let mut filters = [0; 8];
51        let mut filter_count = 0usize;
52        let mut limit = u64::MAX;
53        let mut offset = 0;
54        loop {
55            match plan.operators[operator as usize].operator_type {
56                PhysicalOperatorType::Project {
57                    input,
58                    vars,
59                    var_count,
60                } => {
61                    if projection_count != 0 {
62                        return Err("range join-select does not support nested projections".into());
63                    }
64                    projection = vars;
65                    projection_count = var_count;
66                    operator = input;
67                }
68                PhysicalOperatorType::Limit {
69                    input,
70                    limit: configured,
71                    offset: configured_offset,
72                } => {
73                    if limit != u64::MAX || offset != 0 {
74                        return Err("range join-select does not support nested limits".into());
75                    }
76                    limit = configured;
77                    offset = configured_offset;
78                    operator = input;
79                }
80                PhysicalOperatorType::Filter { input, expression } => {
81                    if filter_count == filters.len() {
82                        return Err(
83                            "range join-select supports at most eight stacked FILTER operators"
84                                .into(),
85                        );
86                    }
87                    filters[filter_count] = expression;
88                    filter_count += 1;
89                    operator = input;
90                }
91                PhysicalOperatorType::NestedLoopJoin { .. } => {
92                    return Ok(Self {
93                        join: Q42RangeNestedLoopJoinPlan::from_join_root(plan, operator)?,
94                        projection,
95                        projection_count,
96                        filters,
97                        filter_count: filter_count as u8,
98                        limit,
99                        offset,
100                    });
101                }
102                PhysicalOperatorType::HashJoin { .. } => {
103                    return Err(
104                        "range join-select does not yet execute HashJoin; planner must emit NestedLoopJoin"
105                            .into(),
106                    );
107                }
108                _ => {
109                    return Err(
110                        "range join-select supports Project/Filter/Limit over NestedLoopJoin(Scan, Scan)"
111                            .into(),
112                    );
113                }
114            }
115        }
116    }
117}
118
119/// Executes a range-join-select into `out`.
120pub fn execute_range_join_select_page_into<S: crate::q42_volume::Q42RangeSource>(
121    volume: &crate::q42_volume::Q42RangeVolume<S>,
122    plan: Q42RangeJoinSelectPlan,
123    ctx: &SparqlQueryContext,
124    state: &mut Q42RangeJoinSelectState,
125    compressed: &mut [u8],
126    decoded: &mut [u8],
127    quin_scratch: &mut [NQuin],
128    left_rows: &mut [BindingRow],
129    right_rows: &mut [BindingRow],
130    join_out: &mut [BindingRow],
131    out: &mut [BindingRow],
132) -> Result<Q42RangeNestedLoopJoinPage, String> {
133    let mut returned = 0usize;
134    loop {
135        if returned == out.len() {
136            return Ok(Q42RangeNestedLoopJoinPage {
137                returned,
138                done: false,
139            });
140        }
141        if state.wrappers.emitted >= plan.limit {
142            return Ok(Q42RangeNestedLoopJoinPage {
143                returned,
144                done: true,
145            });
146        }
147        let page = execute_range_nested_loop_join_page_into(
148            volume,
149            plan.join,
150            ctx,
151            &mut state.join,
152            compressed,
153            decoded,
154            quin_scratch,
155            left_rows,
156            right_rows,
157            join_out,
158        )?;
159        let applied = apply_select_wrappers(
160            ctx,
161            &plan.filters,
162            plan.filter_count,
163            plan.projection,
164            plan.projection_count,
165            plan.limit,
166            plan.offset,
167            &mut state.wrappers,
168            &join_out[..page.returned],
169            &mut out[returned..],
170        )?;
171        returned += applied.returned;
172        if page.done {
173            return Ok(Q42RangeNestedLoopJoinPage {
174                returned,
175                done: true,
176            });
177        }
178        if applied.limit_reached {
179            return Ok(Q42RangeNestedLoopJoinPage {
180                returned,
181                done: true,
182            });
183        }
184        if applied.returned == 0 && !page.done {
185            continue;
186        }
187        if returned > 0 {
188            return Ok(Q42RangeNestedLoopJoinPage {
189                returned,
190                done: false,
191            });
192        }
193    }
194}
195
196/// Executes a volume-set range-join-select into `out`.
197pub fn execute_range_volume_set_join_select_page_into<S: crate::q42_volume::Q42RangeSource>(
198    volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
199    plan: Q42RangeJoinSelectPlan,
200    ctx: &SparqlQueryContext,
201    state: &mut Q42RangeVolumeSetJoinSelectState,
202    compressed: &mut [u8],
203    decoded: &mut [u8],
204    quin_scratch: &mut [NQuin],
205    left_rows: &mut [BindingRow],
206    right_rows: &mut [BindingRow],
207    join_out: &mut [BindingRow],
208    out: &mut [BindingRow],
209) -> Result<Q42RangeNestedLoopJoinPage, String> {
210    let mut returned = 0usize;
211    loop {
212        if returned == out.len() {
213            return Ok(Q42RangeNestedLoopJoinPage {
214                returned,
215                done: false,
216            });
217        }
218        if state.wrappers.emitted >= plan.limit {
219            return Ok(Q42RangeNestedLoopJoinPage {
220                returned,
221                done: true,
222            });
223        }
224        let page = execute_range_volume_set_nested_loop_join_page_into(
225            volumes,
226            plan.join,
227            ctx,
228            &mut state.join,
229            compressed,
230            decoded,
231            quin_scratch,
232            left_rows,
233            right_rows,
234            join_out,
235        )?;
236        let applied = apply_select_wrappers(
237            ctx,
238            &plan.filters,
239            plan.filter_count,
240            plan.projection,
241            plan.projection_count,
242            plan.limit,
243            plan.offset,
244            &mut state.wrappers,
245            &join_out[..page.returned],
246            &mut out[returned..],
247        )?;
248        returned += applied.returned;
249        if page.done || applied.limit_reached {
250            return Ok(Q42RangeNestedLoopJoinPage {
251                returned,
252                done: true,
253            });
254        }
255        if applied.returned == 0 {
256            continue;
257        }
258        if returned > 0 {
259            return Ok(Q42RangeNestedLoopJoinPage {
260                returned,
261                done: false,
262            });
263        }
264    }
265}
266
267#[cfg(test)]
268mod tests {
269    use super::*;
270    use crate::q42_volume::{LocalFileRangeSource, Q42RangeVolume};
271    use crate::sparql_planner::{ExecutionPlan, PhysicalOperatorType};
272
273    #[test]
274    fn peels_project_filter_limit_from_a_join_tree() {
275        let mut plan = ExecutionPlan::new();
276        let left = plan
277            .add_operator(
278                PhysicalOperatorType::TripleScan {
279                    subject: 10,
280                    predicate: 20,
281                    object: 0,
282                },
283                1,
284            )
285            .unwrap();
286        let right = plan
287            .add_operator(
288                PhysicalOperatorType::TripleScan {
289                    subject: 0,
290                    predicate: 40,
291                    object: 50,
292                },
293                1,
294            )
295            .unwrap();
296        let join = plan
297            .add_operator(
298                PhysicalOperatorType::NestedLoopJoin {
299                    left,
300                    right,
301                    join_var: 0,
302                },
303                1,
304            )
305            .unwrap();
306        let limited = plan
307            .add_operator(
308                PhysicalOperatorType::Limit {
309                    input: join,
310                    limit: 1,
311                    offset: 0,
312                },
313                1,
314            )
315            .unwrap();
316        let projected = plan
317            .add_operator(
318                PhysicalOperatorType::Project {
319                    input: limited,
320                    vars: {
321                        let mut vars = [0; MAX_VARIABLES];
322                        vars[0] = 0;
323                        vars
324                    },
325                    var_count: 1,
326                },
327                1,
328            )
329            .unwrap();
330        plan.root_operator = projected;
331        let compiled = Q42RangeJoinSelectPlan::from_execution_plan(&plan).unwrap();
332        assert_eq!(compiled.limit, 1);
333        assert_eq!(compiled.projection_count, 1);
334        assert_eq!(compiled.join.left.subject, 10);
335        assert_eq!(compiled.join.right.object, 50);
336    }
337
338    #[test]
339    fn limit_stops_after_one_join_row() {
340        let dir = tempfile::TempDir::new().unwrap();
341        let path = dir.path().join("join-select.q42");
342        let left = NQuin {
343            subject: 10,
344            predicate: 20,
345            object: 30,
346            context: 0,
347            metadata: 0,
348            parity: 0,
349        };
350        let right = NQuin {
351            subject: 30,
352            predicate: 40,
353            object: 50,
354            context: 0,
355            metadata: 0,
356            parity: 0,
357        };
358        crate::q42_volume::write_unified_volume(
359            &path,
360            &std::collections::HashMap::new(),
361            &[(left.object, right.object)],
362            &[vec![left, right]],
363        )
364        .unwrap();
365        let source = LocalFileRangeSource::open(&path).unwrap();
366        let volume = Q42RangeVolume::open(source).unwrap();
367        let mut context = SparqlQueryContext::new();
368        context.variable_count = 1;
369        let plan = Q42RangeJoinSelectPlan {
370            join: Q42RangeNestedLoopJoinPlan {
371                left: super::super::sparql_executor::Q42RangeTriplePattern {
372                    subject: left.subject,
373                    predicate: left.predicate,
374                    object: 0,
375                },
376                right: super::super::sparql_executor::Q42RangeTriplePattern {
377                    subject: 0,
378                    predicate: right.predicate,
379                    object: right.object,
380                },
381            },
382            projection: {
383                let mut vars = [0; MAX_VARIABLES];
384                vars[0] = 0;
385                vars
386            },
387            projection_count: 1,
388            filters: [0; 8],
389            filter_count: 0,
390            limit: 1,
391            offset: 0,
392        };
393        let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
394        let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
395        let mut quins = [NQuin::default(); 1];
396        let mut left_rows = [BindingRow::default(); 1];
397        let mut right_rows = [BindingRow::default(); 1];
398        let mut join_out = [BindingRow::default(); 1];
399        let mut out = [BindingRow::default(); 1];
400        let mut state = Q42RangeJoinSelectState::default();
401        let page = execute_range_join_select_page_into(
402            &volume,
403            plan,
404            &context,
405            &mut state,
406            &mut compressed,
407            &mut decoded,
408            &mut quins,
409            &mut left_rows,
410            &mut right_rows,
411            &mut join_out,
412            &mut out,
413        )
414        .unwrap();
415        assert_eq!(page.returned, 1);
416        assert!(page.done);
417        assert_eq!(out[0].get(0), Some(right.subject));
418    }
419}