1use crate::sparql_ast::*;
6
7#[repr(C)]
9#[derive(Debug, Clone, Copy, PartialEq, Eq)]
10pub enum PhysicalOperatorType {
11 SubjectScan { subject: u64 },
13 PredicateScan { predicate: u64 },
15 ObjectScan { object: u64 },
17 TripleScan {
19 subject: u64,
20 predicate: u64,
21 object: u64,
22 },
23 HashJoin {
25 left: OperatorId,
26 right: OperatorId,
27 join_var: VariableId,
28 },
29 NestedLoopJoin {
31 left: OperatorId,
32 right: OperatorId,
33 join_var: VariableId,
34 },
35 Filter {
37 input: OperatorId,
38 expression: ExpressionId,
39 },
40 Bind {
44 input: OperatorId,
45 var: VariableId,
46 expression: ExpressionId,
47 },
48 Project {
50 input: OperatorId,
51 vars: [VariableId; MAX_VARIABLES],
52 var_count: u8,
53 },
54 Limit {
56 input: OperatorId,
57 limit: u64,
58 offset: u64,
59 },
60 Sort {
62 input: OperatorId,
63 order_by: [ExpressionId; MAX_ORDER_CONDITIONS],
64 order_count: u8,
65 ascending: [bool; MAX_ORDER_CONDITIONS],
66 },
67 Union { left: OperatorId, right: OperatorId },
69 Optional { left: OperatorId, right: OperatorId },
71 AntiJoin { left: OperatorId, right: OperatorId },
74 Distinct { input: OperatorId },
76 SubSelect { query_id: u16 },
79 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 {
89 input: OperatorId,
90 expression: ExpressionId,
91 },
92 PropertyPath {
94 subject: u64,
95 path_id: PathId,
96 object: u64,
97 },
98 Graph {
100 graph_var_or_id: u64,
101 inner: OperatorId,
102 },
103 Service {
105 endpoint_did_id: u64,
106 inner_pattern: OperatorId,
107 },
108 AsOf {
110 input: OperatorId,
111 timestamp_ms: u64,
112 mode: TemporalMode,
113 },
114 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#[repr(C)]
128#[derive(Debug, Clone, Copy, PartialEq, Eq)]
129pub struct AggregateSpec {
130 pub func: u8, pub input_var: VariableId,
132 pub output_var: VariableId,
133}
134
135#[repr(C)]
137#[derive(Debug, Clone, Copy)]
138pub struct PlanOperator {
139 pub operator_type: PhysicalOperatorType,
140 pub estimated_cardinality: u64,
141}
142
143#[repr(C)]
145pub struct ExecutionPlan {
146 pub operators: [PlanOperator; 64], pub operator_count: u8,
148 pub root_operator: OperatorId,
149}
150
151impl ExecutionPlan {
152 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 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
189pub struct QueryPlanner;
191
192impl QueryPlanner {
193 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 let root_op = Self::plan_pattern(select.root_pattern, ctx, &mut plan)?;
211
212 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 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, )?
255 } else {
256 root_op
257 };
258
259 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 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 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 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 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 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 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 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}