Skip to main content

qualia_core_db/sparql_library/
sparql_planner.rs

1//! SPARQL Logical Query Planner
2//!
3//! Transforms parsed AST into an execution plan using zero-allocation patterns.
4
5use crate::sparql_ast::*;
6
7/// Physical operator types for the execution plan
8#[repr(C)]
9#[derive(Debug, Clone, Copy, PartialEq, Eq)]
10pub enum PhysicalOperatorType {
11    /// Scan all quins matching a subject
12    SubjectScan { subject: u64 },
13    /// Scan all quins matching a predicate
14    PredicateScan { predicate: u64 },
15    /// Scan all quins matching an object
16    ObjectScan { object: u64 },
17    /// Triple pattern scan with all three components
18    TripleScan {
19        subject: u64,
20        predicate: u64,
21        object: u64,
22    },
23    /// Hash join between two operators
24    HashJoin {
25        left: OperatorId,
26        right: OperatorId,
27        join_var: VariableId,
28    },
29    /// Nested loop join for small datasets
30    NestedLoopJoin {
31        left: OperatorId,
32        right: OperatorId,
33        join_var: VariableId,
34    },
35    /// Filter operator
36    Filter {
37        input: OperatorId,
38        expression: ExpressionId,
39    },
40    /// Bind operator — extends each input row with `var` = eval(`expression`)
41    /// (SPARQL 1.1 Extend). Never drops rows; an expression error leaves the
42    /// variable unbound.
43    Bind {
44        input: OperatorId,
45        var: VariableId,
46        expression: ExpressionId,
47    },
48    /// Projection operator
49    Project {
50        input: OperatorId,
51        vars: [VariableId; MAX_VARIABLES],
52        var_count: u8,
53    },
54    /// Limit operator
55    Limit {
56        input: OperatorId,
57        limit: u64,
58        offset: u64,
59    },
60    /// Sort operator
61    Sort {
62        input: OperatorId,
63        order_by: [ExpressionId; MAX_ORDER_CONDITIONS],
64        order_count: u8,
65        ascending: [bool; MAX_ORDER_CONDITIONS],
66    },
67    /// Union operator
68    Union { left: OperatorId, right: OperatorId },
69    /// Optional operator (SPARQL 1.1 left-join)
70    Optional { left: OperatorId, right: OperatorId },
71    /// Anti-join operator (SPARQL 1.1 MINUS): keep a left solution unless a
72    /// right solution is compatible with it AND shares a bound variable.
73    AntiJoin { left: OperatorId, right: OperatorId },
74    /// Distinct operator
75    Distinct { input: OperatorId },
76    /// Sub-SELECT: evaluate stored subquery `query_id` independently and join
77    /// its projected solutions with the enclosing bindings.
78    SubSelect { query_id: u16 },
79    /// GroupBy operator with Aggregates
80    GroupBy {
81        input: OperatorId,
82        group_vars: [VariableId; MAX_VARIABLES],
83        group_var_count: u8,
84        aggregates: [AggregateSpec; 16],
85        aggregate_count: u8,
86    },
87    /// Having operator
88    Having {
89        input: OperatorId,
90        expression: ExpressionId,
91    },
92    /// Property path operator
93    PropertyPath {
94        subject: u64,
95        path_id: PathId,
96        object: u64,
97    },
98    /// Graph operator
99    Graph {
100        graph_var_or_id: u64,
101        inner: OperatorId,
102    },
103    /// Service operator (Federated Query with DID)
104    Service {
105        endpoint_did_id: u64,
106        inner_pattern: OperatorId,
107    },
108    /// AS OF / AT TIME temporal snapshot operator (Phase 4).
109    AsOf {
110        input: OperatorId,
111        timestamp_ms: u64,
112        mode: TemporalMode,
113    },
114    /// RDF-Star annotation triple scan.
115    StarTripleScan {
116        inner_subject: u64,
117        inner_predicate: u64,
118        inner_object: u64,
119        outer_predicate: u64,
120        outer_object: u64,
121    },
122}
123
124pub type OperatorId = u16;
125
126/// Aggregate specification
127#[repr(C)]
128#[derive(Debug, Clone, Copy, PartialEq, Eq)]
129pub struct AggregateSpec {
130    pub func: u8, // 0=COUNT, 1=SUM, 2=AVG, 3=MIN, 4=MAX
131    pub input_var: VariableId,
132    pub output_var: VariableId,
133}
134
135/// Execution plan operator
136#[repr(C)]
137#[derive(Debug, Clone, Copy)]
138pub struct PlanOperator {
139    pub operator_type: PhysicalOperatorType,
140    pub estimated_cardinality: u64,
141}
142
143/// Execution plan
144#[repr(C)]
145pub struct ExecutionPlan {
146    pub operators: [PlanOperator; 64], // Max 64 operators in a plan
147    pub operator_count: u8,
148    pub root_operator: OperatorId,
149}
150
151impl ExecutionPlan {
152    /// Creates a default `ExecutionPlan`.
153    pub fn new() -> Self {
154        Self {
155            operators: [PlanOperator {
156                operator_type: PhysicalOperatorType::SubjectScan { subject: 0 },
157                estimated_cardinality: 0,
158            }; 64],
159            operator_count: 0,
160            root_operator: 0,
161        }
162    }
163
164    /// Adds `operator`.
165    pub fn add_operator(
166        &mut self,
167        op: PhysicalOperatorType,
168        cardinality: u64,
169    ) -> Result<OperatorId, String> {
170        if self.operator_count >= 64 {
171            return Err("Operator overflow".to_string());
172        }
173        let id = self.operator_count as OperatorId;
174        self.operators[self.operator_count as usize] = PlanOperator {
175            operator_type: op,
176            estimated_cardinality: cardinality,
177        };
178        self.operator_count += 1;
179        Ok(id)
180    }
181}
182
183impl Default for ExecutionPlan {
184    fn default() -> Self {
185        Self::new()
186    }
187}
188
189/// Query planner
190pub struct QueryPlanner;
191
192impl QueryPlanner {
193    /// Plan a SPARQL query into an execution plan
194    pub fn plan(query: &SparqlQuery, ctx: &SparqlQueryContext) -> Result<ExecutionPlan, String> {
195        match query {
196            SparqlQuery::Select(select) => Self::plan_select(select, ctx),
197            SparqlQuery::Ask(ask) => Self::plan_ask(ask, ctx),
198            SparqlQuery::Construct(construct) => Self::plan_construct(construct, ctx),
199            SparqlQuery::Describe(describe) => Self::plan_describe(describe, ctx),
200        }
201    }
202
203    fn plan_select(
204        select: &SelectQuery,
205        ctx: &SparqlQueryContext,
206    ) -> Result<ExecutionPlan, String> {
207        let mut plan = ExecutionPlan::new();
208
209        // Plan the WHERE clause
210        let root_op = Self::plan_pattern(select.root_pattern, ctx, &mut plan)?;
211
212        // Apply GroupBy/Aggregates
213        let group_op = if select.group_by_count > 0 || select.aggregate_count > 0 {
214            let mut group_vars = [0u8; MAX_VARIABLES];
215            if select.group_by_count > 0 {
216                group_vars[..select.group_by_count as usize]
217                    .copy_from_slice(&select.group_by[..select.group_by_count as usize]);
218            }
219            let mut aggregates = [crate::sparql_planner::AggregateSpec {
220                func: 0,
221                input_var: 0,
222                output_var: 0,
223            }; 16];
224            if select.aggregate_count > 0 {
225                aggregates[..select.aggregate_count as usize]
226                    .copy_from_slice(&select.aggregates[..select.aggregate_count as usize]);
227            }
228            plan.add_operator(
229                PhysicalOperatorType::GroupBy {
230                    input: root_op,
231                    group_vars,
232                    group_var_count: select.group_by_count,
233                    aggregates,
234                    aggregate_count: select.aggregate_count,
235                },
236                0,
237            )?
238        } else {
239            root_op
240        };
241
242        // Apply projection
243        let project_op = if select.var_count > 0 {
244            let mut vars = [0u8; MAX_VARIABLES];
245            vars[..select.var_count as usize]
246                .copy_from_slice(&select.variables[..select.var_count as usize]);
247            plan.add_operator(
248                PhysicalOperatorType::Project {
249                    input: group_op,
250                    vars,
251                    var_count: select.var_count,
252                },
253                0, // Cardinality unknown
254            )?
255        } else {
256            root_op
257        };
258
259        // Apply DISTINCT / REDUCED — dedup the projected solutions. (Previously
260        // the `distinct` flag was parsed but never planned, so `SELECT DISTINCT`
261        // silently returned duplicates.) Eliminating all duplicates is also a
262        // conformant realisation of REDUCED.
263        let distinct_op = if select.distinct || select.reduced {
264            plan.add_operator(PhysicalOperatorType::Distinct { input: project_op }, 0)?
265        } else {
266            project_op
267        };
268
269        // Apply sorting
270        let sort_op = if select.order_by_count > 0 {
271            let mut order_by = [0u16; MAX_ORDER_CONDITIONS];
272            let mut ascending = [true; MAX_ORDER_CONDITIONS];
273            for i in 0..select.order_by_count as usize {
274                order_by[i] = select.order_by[i].expr;
275                ascending[i] = select.order_by[i].ascending;
276            }
277            plan.add_operator(
278                PhysicalOperatorType::Sort {
279                    input: distinct_op,
280                    order_by,
281                    order_count: select.order_by_count,
282                    ascending,
283                },
284                0,
285            )?
286        } else {
287            distinct_op
288        };
289
290        // Apply limit/offset
291        let final_op = if select.limit.is_some() || select.offset > 0 {
292            plan.add_operator(
293                PhysicalOperatorType::Limit {
294                    input: sort_op,
295                    limit: select.limit.unwrap_or(u64::MAX),
296                    offset: select.offset,
297                },
298                0,
299            )?
300        } else {
301            sort_op
302        };
303
304        plan.root_operator = final_op;
305        Ok(plan)
306    }
307
308    fn plan_ask(ask: &AskQuery, ctx: &SparqlQueryContext) -> Result<ExecutionPlan, String> {
309        let mut plan = ExecutionPlan::new();
310        let root_op = Self::plan_pattern(ask.root_pattern, ctx, &mut plan)?;
311        plan.root_operator = root_op;
312        Ok(plan)
313    }
314
315    fn plan_construct(
316        construct: &ConstructQuery,
317        ctx: &SparqlQueryContext,
318    ) -> Result<ExecutionPlan, String> {
319        let mut plan = ExecutionPlan::new();
320        let root_op = Self::plan_pattern(construct.root_pattern, ctx, &mut plan)?;
321        plan.root_operator = root_op;
322        Ok(plan)
323    }
324
325    fn plan_describe(
326        describe: &DescribeQuery,
327        ctx: &SparqlQueryContext,
328    ) -> Result<ExecutionPlan, String> {
329        let mut plan = ExecutionPlan::new();
330        if let Some(pattern_id) = describe.root_pattern {
331            let root_op = Self::plan_pattern(pattern_id, ctx, &mut plan)?;
332            plan.root_operator = root_op;
333        }
334        Ok(plan)
335    }
336
337    /// Plans a triple pattern.
338    pub(crate) fn plan_pattern(
339        pattern_id: PatternId,
340        ctx: &SparqlQueryContext,
341        plan: &mut ExecutionPlan,
342    ) -> Result<OperatorId, String> {
343        let pattern = ctx
344            .patterns
345            .get(pattern_id as usize)
346            .ok_or("Pattern ID out of bounds")?;
347
348        match pattern {
349            Pattern::Triple {
350                subject,
351                predicate,
352                object,
353            } => plan.add_operator(
354                PhysicalOperatorType::TripleScan {
355                    subject: *subject,
356                    predicate: *predicate,
357                    object: *object,
358                },
359                0,
360            ),
361            Pattern::StarTriple {
362                inner_subject,
363                inner_predicate,
364                inner_object,
365                outer_predicate,
366                outer_object,
367            } => plan.add_operator(
368                PhysicalOperatorType::StarTripleScan {
369                    inner_subject: *inner_subject,
370                    inner_predicate: *inner_predicate,
371                    inner_object: *inner_object,
372                    outer_predicate: *outer_predicate,
373                    outer_object: *outer_object,
374                },
375                0,
376            ),
377            Pattern::Optional { inner } => {
378                let inner_op = Self::plan_pattern(*inner, ctx, plan)?;
379                // For now, just return the inner operator (simplified)
380                Ok(inner_op)
381            }
382            Pattern::Union { left, right } => {
383                let left_op = Self::plan_pattern(*left, ctx, plan)?;
384                let right_op = Self::plan_pattern(*right, ctx, plan)?;
385                plan.add_operator(
386                    PhysicalOperatorType::Union {
387                        left: left_op,
388                        right: right_op,
389                    },
390                    0,
391                )
392            }
393
394            Pattern::Filter {
395                pattern: inner_pattern,
396                expression,
397            } => {
398                let inner_op = Self::plan_pattern(*inner_pattern, ctx, plan)?;
399                plan.add_operator(
400                    PhysicalOperatorType::Filter {
401                        input: inner_op,
402                        expression: *expression,
403                    },
404                    0,
405                )
406            }
407            Pattern::Bind {
408                pattern: inner_pattern,
409                var,
410                expression,
411            } => {
412                let inner_op = Self::plan_pattern(*inner_pattern, ctx, plan)?;
413                plan.add_operator(
414                    PhysicalOperatorType::Bind {
415                        input: inner_op,
416                        var: *var,
417                        expression: *expression,
418                    },
419                    0,
420                )
421            }
422            Pattern::Minus { inner } => Self::plan_pattern(*inner, ctx, plan),
423            Pattern::Group { start_idx, len } => {
424                // Plan the group's children left-to-right. Plain children join
425                // (natural join — the nested-loop operator checks compatibility
426                // across all bound slots). OPTIONAL children become a real
427                // left-join and MINUS children a real anti-join against the
428                // accumulated result, rather than being folded into a plain join
429                // (which would make OPTIONAL required and MINUS behave like an
430                // intersection — both wrong).
431                let mut current_op: Option<OperatorId> = None;
432                for i in *start_idx..(*start_idx + *len) {
433                    let child = ctx
434                        .patterns
435                        .get(i as usize)
436                        .ok_or("Pattern ID out of bounds")?;
437                    match child {
438                        Pattern::Optional { inner } => {
439                            let right = Self::plan_pattern(*inner, ctx, plan)?;
440                            current_op = Some(match current_op {
441                                Some(left) => plan.add_operator(
442                                    PhysicalOperatorType::Optional { left, right },
443                                    0,
444                                )?,
445                                // A leading OPTIONAL has no required left side —
446                                // its solutions stand alone.
447                                None => right,
448                            });
449                        }
450                        Pattern::Minus { inner } => {
451                            let right = Self::plan_pattern(*inner, ctx, plan)?;
452                            current_op = Some(match current_op {
453                                Some(left) => plan.add_operator(
454                                    PhysicalOperatorType::AntiJoin { left, right },
455                                    0,
456                                )?,
457                                // MINUS with nothing to subtract from is
458                                // degenerate (malformed SPARQL); nothing is
459                                // removed, so fall back to the inner solutions.
460                                None => right,
461                            });
462                        }
463                        _ => {
464                            let pattern_op = Self::plan_pattern(i, ctx, plan)?;
465                            current_op = Some(match current_op {
466                                Some(curr) => plan.add_operator(
467                                    PhysicalOperatorType::NestedLoopJoin {
468                                        left: curr,
469                                        right: pattern_op,
470                                        join_var: 0,
471                                    },
472                                    0,
473                                )?,
474                                None => pattern_op,
475                            });
476                        }
477                    }
478                }
479                current_op.ok_or("Empty group pattern".to_string())
480            }
481            Pattern::PropertyPath {
482                subject,
483                path,
484                object,
485            } => plan.add_operator(
486                PhysicalOperatorType::PropertyPath {
487                    subject: *subject,
488                    path_id: *path,
489                    object: *object,
490                },
491                0,
492            ),
493            Pattern::SubSelect { query_id } => plan.add_operator(
494                PhysicalOperatorType::SubSelect {
495                    query_id: *query_id,
496                },
497                0,
498            ),
499            Pattern::Graph {
500                graph_var_or_id,
501                inner,
502            } => {
503                let inner_op = Self::plan_pattern(*inner, ctx, plan)?;
504                plan.add_operator(
505                    PhysicalOperatorType::Graph {
506                        graph_var_or_id: *graph_var_or_id,
507                        inner: inner_op,
508                    },
509                    0,
510                )
511            }
512            Pattern::Service {
513                endpoint_did_id,
514                inner_pattern,
515            } => {
516                let inner_op = Self::plan_pattern(*inner_pattern, ctx, plan)?;
517                plan.add_operator(
518                    PhysicalOperatorType::Service {
519                        endpoint_did_id: *endpoint_did_id,
520                        inner_pattern: inner_op,
521                    },
522                    0,
523                )
524            }
525            Pattern::AsOf {
526                inner,
527                timestamp_ms,
528                mode,
529            } => {
530                let inner_op = Self::plan_pattern(*inner, ctx, plan)?;
531                plan.add_operator(
532                    PhysicalOperatorType::AsOf {
533                        input: inner_op,
534                        timestamp_ms: *timestamp_ms,
535                        mode: *mode,
536                    },
537                    0,
538                )
539            }
540        }
541    }
542}
543
544#[cfg(test)]
545mod tests {
546    use super::*;
547
548    #[test]
549    fn test_execution_plan_creation() {
550        let plan = ExecutionPlan::new();
551        assert_eq!(plan.operator_count, 0);
552    }
553
554    #[test]
555    fn test_add_operator() {
556        let mut plan = ExecutionPlan::new();
557        let op = PhysicalOperatorType::SubjectScan { subject: 42 };
558        let id = plan.add_operator(op, 0).unwrap();
559        assert_eq!(id, 0);
560        assert_eq!(plan.operator_count, 1);
561    }
562
563    #[test]
564    fn test_plan_triple_pattern() {
565        let mut ctx = SparqlQueryContext::new();
566        let pattern = Pattern::Triple {
567            subject: 1,
568            predicate: 2,
569            object: 3,
570        };
571        let pattern_id = ctx.alloc_pattern(pattern).unwrap();
572
573        let mut plan = ExecutionPlan::new();
574        let op_id = QueryPlanner::plan_pattern(pattern_id, &ctx, &mut plan).unwrap();
575        assert_eq!(op_id, 0);
576        assert_eq!(plan.operator_count, 1);
577    }
578}