lora_compiler/
plan_tree.rs

1//! Public-API-friendly mirror of a [`CompiledQuery`]'s operator tree.
2//!
3//! `PlanTree` walks the physical plan and produces a flat, serializable
4//! description suitable for surfacing through `Database::explain` /
5//! `Database::profile` and onwards through the language bindings.
6//!
7//! The internal `PhysicalOp` nodes reference analyzer-internal types
8//! (`ResolvedExpr`, `VarId`); we deliberately do not expose those. Each
9//! operator becomes a `PlanTreeNode` with an opaque, human-readable
10//! `details` map keyed on stable strings. Future cost-modelling can fill
11//! in `estimated_rows` without breaking the type.
12use std::collections::BTreeMap;
13use std::fmt::Write as _;
14
15use lora_analyzer::{ResolvedExpr, ResolvedProjection};
16use lora_ast::Direction;
17
18use crate::physical::{PhysicalNodeId, PhysicalOp, PhysicalPlan};
19use crate::{CompiledQuery, CompiledUnionBranch};
20
21/// One node in the rendered plan tree.
22#[derive(Debug, Clone)]
23pub struct PlanTreeNode {
24    /// Stable `PhysicalNodeId` within the owning plan. Synthetic
25    /// nodes (e.g. the Union root, branch wrappers) reuse a sentinel
26    /// id of `usize::MAX`.
27    pub id: usize,
28    /// Operator label, e.g. `NodeByLabelScan`, `Expand`, `Projection`.
29    pub operator: String,
30    /// Human-readable operator details. Values are stringified so the
31    /// public API never leaks internal expression / `VarId` types.
32    pub details: BTreeMap<String, String>,
33    /// Reserved for a future cost model. Always `None` today.
34    pub estimated_rows: Option<u64>,
35    /// Children in physical execution order (leaf-most first).
36    pub children: Vec<PlanTreeNode>,
37}
38
39/// Top-level plan tree.
40#[derive(Debug, Clone)]
41pub struct PlanTree {
42    pub root: PlanTreeNode,
43}
44
45const SYNTHETIC_ID: usize = usize::MAX;
46
47/// Build a `PlanTree` from a compiled query, including UNION branches.
48pub fn plan_tree_from_compiled(compiled: &CompiledQuery) -> PlanTree {
49    let head = build_node(&compiled.physical, compiled.physical.root);
50    if compiled.unions.is_empty() {
51        return PlanTree { root: head };
52    }
53
54    let mut children = Vec::with_capacity(compiled.unions.len() + 1);
55    children.push(head);
56    for branch in &compiled.unions {
57        children.push(build_union_branch(branch));
58    }
59    let mut details = BTreeMap::new();
60    details.insert("kind".to_string(), union_kind(&compiled.unions).to_string());
61    PlanTree {
62        root: PlanTreeNode {
63            id: SYNTHETIC_ID,
64            operator: "Union".to_string(),
65            details,
66            estimated_rows: None,
67            children,
68        },
69    }
70}
71
72fn build_union_branch(branch: &CompiledUnionBranch) -> PlanTreeNode {
73    let mut details = BTreeMap::new();
74    details.insert(
75        "kind".to_string(),
76        if branch.all { "ALL" } else { "DISTINCT" }.to_string(),
77    );
78    PlanTreeNode {
79        id: SYNTHETIC_ID,
80        operator: "UnionBranch".to_string(),
81        details,
82        estimated_rows: None,
83        children: vec![build_node(&branch.physical, branch.physical.root)],
84    }
85}
86
87fn build_node(plan: &PhysicalPlan, id: PhysicalNodeId) -> PlanTreeNode {
88    let op = &plan.nodes[id];
89    let description = describe(op);
90    let children = description
91        .child_ids
92        .into_iter()
93        .map(|cid| build_node(plan, cid))
94        .collect();
95    PlanTreeNode {
96        id,
97        operator: description.operator,
98        details: description.details,
99        estimated_rows: None,
100        children,
101    }
102}
103
104struct PlanDescription {
105    operator: String,
106    details: BTreeMap<String, String>,
107    child_ids: Vec<PhysicalNodeId>,
108}
109
110impl PlanDescription {
111    fn leaf(operator: &str) -> Self {
112        Self::new(operator, BTreeMap::new(), Vec::new())
113    }
114
115    fn with_children(
116        operator: &str,
117        details: BTreeMap<String, String>,
118        child_ids: Vec<PhysicalNodeId>,
119    ) -> Self {
120        Self::new(operator, details, child_ids)
121    }
122
123    fn new(
124        operator: &str,
125        details: BTreeMap<String, String>,
126        child_ids: Vec<PhysicalNodeId>,
127    ) -> Self {
128        Self {
129            operator: operator.to_string(),
130            details,
131            child_ids,
132        }
133    }
134}
135
136fn describe(op: &PhysicalOp) -> PlanDescription {
137    let mut d = BTreeMap::new();
138    match op {
139        PhysicalOp::Argument(_) => PlanDescription::leaf("Argument"),
140        PhysicalOp::NodeScan(n) => {
141            d.insert("var".to_string(), var_str(n.var));
142            PlanDescription::with_children("NodeScan", d, opt_input(n.input))
143        }
144        PhysicalOp::NodeByLabelScan(n) => {
145            d.insert("var".to_string(), var_str(n.var));
146            d.insert("labels".to_string(), label_groups_str(&n.labels));
147            PlanDescription::with_children("NodeByLabelScan", d, opt_input(n.input))
148        }
149        PhysicalOp::NodeByPropertyScan(n) => {
150            d.insert("var".to_string(), var_str(n.var));
151            if !n.labels.is_empty() {
152                d.insert("labels".to_string(), label_groups_str(&n.labels));
153            }
154            d.insert("key".to_string(), n.key.clone());
155            d.insert("value".to_string(), expr_str(&n.value));
156            PlanDescription::with_children("NodeByPropertyScan", d, opt_input(n.input))
157        }
158        PhysicalOp::NodeByPropertyRangeScan(n) => {
159            d.insert("var".to_string(), var_str(n.var));
160            if !n.labels.is_empty() {
161                d.insert("labels".to_string(), label_groups_str(&n.labels));
162            }
163            d.insert("key".to_string(), n.key.clone());
164            if let Some(lo) = &n.lo {
165                d.insert(
166                    "lo".to_string(),
167                    format!(
168                        "{} {}",
169                        if n.lo_inclusive { ">=" } else { ">" },
170                        expr_str(lo)
171                    ),
172                );
173            }
174            if let Some(hi) = &n.hi {
175                d.insert(
176                    "hi".to_string(),
177                    format!(
178                        "{} {}",
179                        if n.hi_inclusive { "<=" } else { "<" },
180                        expr_str(hi)
181                    ),
182                );
183            }
184            PlanDescription::with_children("NodeByPropertyRangeScan", d, opt_input(n.input))
185        }
186        PhysicalOp::NodeByPointScan(n) => {
187            d.insert("var".to_string(), var_str(n.var));
188            if !n.labels.is_empty() {
189                d.insert("labels".to_string(), label_groups_str(&n.labels));
190            }
191            d.insert("key".to_string(), n.key.clone());
192            match &n.predicate {
193                crate::PointPredicate::WithinBBox {
194                    lower_left,
195                    upper_right,
196                } => {
197                    d.insert("predicate".to_string(), "withinBBox".to_string());
198                    d.insert("lowerLeft".to_string(), expr_str(lower_left));
199                    d.insert("upperRight".to_string(), expr_str(upper_right));
200                }
201                crate::PointPredicate::WithinDistance {
202                    center,
203                    max_distance,
204                    inclusive,
205                } => {
206                    d.insert(
207                        "predicate".to_string(),
208                        if *inclusive {
209                            "distance<="
210                        } else {
211                            "distance<"
212                        }
213                        .to_string(),
214                    );
215                    d.insert("center".to_string(), expr_str(center));
216                    d.insert("maxDistance".to_string(), expr_str(max_distance));
217                }
218            }
219            PlanDescription::with_children("NodeByPointScan", d, opt_input(n.input))
220        }
221        PhysicalOp::NodeByTextScan(n) => {
222            d.insert("var".to_string(), var_str(n.var));
223            if !n.labels.is_empty() {
224                d.insert("labels".to_string(), label_groups_str(&n.labels));
225            }
226            d.insert("key".to_string(), n.key.clone());
227            d.insert(
228                "predicate".to_string(),
229                match n.predicate {
230                    crate::TextPredicate::StartsWith => "STARTS WITH",
231                    crate::TextPredicate::EndsWith => "ENDS WITH",
232                    crate::TextPredicate::Contains => "CONTAINS",
233                }
234                .to_string(),
235            );
236            d.insert("query".to_string(), expr_str(&n.query));
237            PlanDescription::with_children("NodeByTextScan", d, opt_input(n.input))
238        }
239        PhysicalOp::RelByPropertyRangeScan(n) => {
240            d.insert("rel".to_string(), var_str(n.rel));
241            d.insert("src".to_string(), var_str(n.src));
242            d.insert("dst".to_string(), var_str(n.dst));
243            if !n.types.is_empty() {
244                d.insert("types".to_string(), n.types.join("|"));
245            }
246            d.insert(
247                "direction".to_string(),
248                direction_str(n.direction).to_string(),
249            );
250            d.insert("key".to_string(), n.key.clone());
251            if let Some(lo) = &n.lo {
252                d.insert(
253                    "lo".to_string(),
254                    format!(
255                        "{} {}",
256                        if n.lo_inclusive { ">=" } else { ">" },
257                        expr_str(lo)
258                    ),
259                );
260            }
261            if let Some(hi) = &n.hi {
262                d.insert(
263                    "hi".to_string(),
264                    format!(
265                        "{} {}",
266                        if n.hi_inclusive { "<=" } else { "<" },
267                        expr_str(hi)
268                    ),
269                );
270            }
271            PlanDescription::with_children("RelByPropertyRangeScan", d, opt_input(n.input))
272        }
273        PhysicalOp::RelByTextScan(n) => {
274            d.insert("rel".to_string(), var_str(n.rel));
275            d.insert("src".to_string(), var_str(n.src));
276            d.insert("dst".to_string(), var_str(n.dst));
277            if !n.types.is_empty() {
278                d.insert("types".to_string(), n.types.join("|"));
279            }
280            d.insert(
281                "direction".to_string(),
282                direction_str(n.direction).to_string(),
283            );
284            d.insert("key".to_string(), n.key.clone());
285            d.insert(
286                "predicate".to_string(),
287                match n.predicate {
288                    crate::TextPredicate::StartsWith => "STARTS WITH",
289                    crate::TextPredicate::EndsWith => "ENDS WITH",
290                    crate::TextPredicate::Contains => "CONTAINS",
291                }
292                .to_string(),
293            );
294            d.insert("query".to_string(), expr_str(&n.query));
295            PlanDescription::with_children("RelByTextScan", d, opt_input(n.input))
296        }
297        PhysicalOp::RelByPointScan(n) => {
298            d.insert("rel".to_string(), var_str(n.rel));
299            d.insert("src".to_string(), var_str(n.src));
300            d.insert("dst".to_string(), var_str(n.dst));
301            if !n.types.is_empty() {
302                d.insert("types".to_string(), n.types.join("|"));
303            }
304            d.insert(
305                "direction".to_string(),
306                direction_str(n.direction).to_string(),
307            );
308            d.insert("key".to_string(), n.key.clone());
309            match &n.predicate {
310                crate::PointPredicate::WithinBBox {
311                    lower_left,
312                    upper_right,
313                } => {
314                    d.insert("predicate".to_string(), "withinBBox".to_string());
315                    d.insert("lowerLeft".to_string(), expr_str(lower_left));
316                    d.insert("upperRight".to_string(), expr_str(upper_right));
317                }
318                crate::PointPredicate::WithinDistance {
319                    center,
320                    max_distance,
321                    inclusive,
322                } => {
323                    d.insert(
324                        "predicate".to_string(),
325                        if *inclusive {
326                            "distance<="
327                        } else {
328                            "distance<"
329                        }
330                        .to_string(),
331                    );
332                    d.insert("center".to_string(), expr_str(center));
333                    d.insert("maxDistance".to_string(), expr_str(max_distance));
334                }
335            }
336            PlanDescription::with_children("RelByPointScan", d, opt_input(n.input))
337        }
338        PhysicalOp::Expand(n) => describe_expand(n),
339        PhysicalOp::Filter(n) => {
340            d.insert("predicate".to_string(), expr_str(&n.predicate));
341            PlanDescription::with_children("Filter", d, vec![n.input])
342        }
343        PhysicalOp::Projection(n) => describe_projection(n),
344        PhysicalOp::Unwind(n) => {
345            d.insert("alias".to_string(), var_str(n.alias));
346            d.insert("expr".to_string(), expr_str(&n.expr));
347            PlanDescription::with_children("Unwind", d, vec![n.input])
348        }
349        PhysicalOp::HashAggregation(n) => describe_hash_aggregation(n),
350        PhysicalOp::Sort(n) => {
351            d.insert(
352                "items".to_string(),
353                format!("{} sort key(s)", n.items.len()),
354            );
355            if let Some(top_k) = n.top_k {
356                d.insert("top_k".to_string(), top_k.to_string());
357            }
358            PlanDescription::with_children("Sort", d, vec![n.input])
359        }
360        PhysicalOp::Limit(n) => {
361            if let Some(skip) = &n.skip {
362                d.insert("skip".to_string(), expr_str(skip));
363            }
364            if let Some(limit) = &n.limit {
365                d.insert("limit".to_string(), expr_str(limit));
366            }
367            PlanDescription::with_children("Limit", d, vec![n.input])
368        }
369        PhysicalOp::Create(n) => {
370            d.insert(
371                "elements".to_string(),
372                pattern_summary(n.pattern.parts.len()),
373            );
374            PlanDescription::with_children("Create", d, vec![n.input])
375        }
376        PhysicalOp::Merge(n) => describe_merge(n),
377        PhysicalOp::Delete(n) => {
378            d.insert("detach".to_string(), n.detach.to_string());
379            d.insert("targets".to_string(), n.expressions.len().to_string());
380            PlanDescription::with_children("Delete", d, vec![n.input])
381        }
382        PhysicalOp::Set(n) => {
383            d.insert("items".to_string(), n.items.len().to_string());
384            PlanDescription::with_children("Set", d, vec![n.input])
385        }
386        PhysicalOp::Remove(n) => {
387            d.insert("items".to_string(), n.items.len().to_string());
388            PlanDescription::with_children("Remove", d, vec![n.input])
389        }
390        PhysicalOp::OptionalMatch(n) => describe_optional_match(n),
391        PhysicalOp::CallSubquery(n) => {
392            d.insert(
393                "new_vars".to_string(),
394                n.new_vars
395                    .iter()
396                    .copied()
397                    .map(var_str)
398                    .collect::<Vec<_>>()
399                    .join(", "),
400            );
401            PlanDescription::with_children("CallSubquery", d, vec![n.input, n.inner])
402        }
403        PhysicalOp::PathBuild(n) => {
404            d.insert("output".to_string(), var_str(n.output));
405            d.insert("nodes".to_string(), n.node_vars.len().to_string());
406            d.insert("rels".to_string(), n.rel_vars.len().to_string());
407            if let Some(all) = n.shortest_path_all {
408                d.insert("shortest_path_all".to_string(), all.to_string());
409            }
410            PlanDescription::with_children("PathBuild", d, vec![n.input])
411        }
412    }
413}
414
415fn union_kind(branches: &[CompiledUnionBranch]) -> &'static str {
416    let all = branches.iter().all(|b| b.all);
417    let all_distinct = branches.iter().all(|b| !b.all);
418    if all {
419        "ALL"
420    } else if all_distinct {
421        "DISTINCT"
422    } else {
423        "MIXED"
424    }
425}
426
427fn describe_expand(n: &crate::physical::ExpandExec) -> PlanDescription {
428    let mut d = BTreeMap::new();
429    d.insert("src".to_string(), var_str(n.src));
430    d.insert("dst".to_string(), var_str(n.dst));
431    if let Some(rel) = n.rel {
432        d.insert("rel".to_string(), var_str(rel));
433    }
434    if !n.types.is_empty() {
435        d.insert("types".to_string(), n.types.join("|"));
436    }
437    d.insert(
438        "direction".to_string(),
439        direction_str(n.direction).to_string(),
440    );
441    if let Some(props) = &n.rel_properties {
442        d.insert("rel_properties".to_string(), expr_str(props));
443    }
444    if let Some(range) = &n.range {
445        d.insert("range".to_string(), format!("{:?}", range));
446    }
447    PlanDescription::with_children("Expand", d, vec![n.input])
448}
449
450fn describe_projection(n: &crate::physical::ProjectionExec) -> PlanDescription {
451    let mut d = BTreeMap::new();
452    d.insert("distinct".to_string(), n.distinct.to_string());
453    d.insert(
454        "include_existing".to_string(),
455        n.include_existing.to_string(),
456    );
457    d.insert("items".to_string(), projection_names(&n.items));
458    PlanDescription::with_children("Projection", d, vec![n.input])
459}
460
461fn describe_hash_aggregation(n: &crate::physical::HashAggregationExec) -> PlanDescription {
462    let mut d = BTreeMap::new();
463    d.insert("group_by".to_string(), projection_names(&n.group_by));
464    d.insert("aggregates".to_string(), projection_names(&n.aggregates));
465    PlanDescription::with_children("HashAggregation", d, vec![n.input])
466}
467
468fn describe_merge(n: &crate::physical::MergeExec) -> PlanDescription {
469    let mut d = BTreeMap::new();
470    d.insert("actions".to_string(), n.actions.len().to_string());
471    PlanDescription::with_children("Merge", d, vec![n.input])
472}
473
474fn describe_optional_match(n: &crate::physical::OptionalMatchExec) -> PlanDescription {
475    let mut d = BTreeMap::new();
476    d.insert(
477        "new_vars".to_string(),
478        n.new_vars
479            .iter()
480            .copied()
481            .map(var_str)
482            .collect::<Vec<_>>()
483            .join(", "),
484    );
485    PlanDescription::with_children("OptionalMatch", d, vec![n.input, n.inner])
486}
487
488fn opt_input(input: Option<PhysicalNodeId>) -> Vec<PhysicalNodeId> {
489    input.map(|i| vec![i]).unwrap_or_default()
490}
491
492fn var_str(v: lora_analyzer::symbols::VarId) -> String {
493    format!("v{}", v.0)
494}
495
496fn label_groups_str(groups: &[Vec<String>]) -> String {
497    groups
498        .iter()
499        .map(|or_group| or_group.join("|"))
500        .collect::<Vec<_>>()
501        .join("&")
502}
503
504fn projection_names(items: &[ResolvedProjection]) -> String {
505    items
506        .iter()
507        .map(|p| p.name.clone())
508        .collect::<Vec<_>>()
509        .join(", ")
510}
511
512fn direction_str(d: Direction) -> &'static str {
513    match d {
514        Direction::Right => "->",
515        Direction::Left => "<-",
516        Direction::Undirected => "-",
517    }
518}
519
520fn expr_str(e: &ResolvedExpr) -> String {
521    let mut out = String::new();
522    let _ = write!(&mut out, "{:?}", e);
523    out
524}
525
526fn pattern_summary(part_count: usize) -> String {
527    format!("{} pattern part(s)", part_count)
528}
lora_compiler/plan_tree.rs

lora_compiler/
plan_tree.rs
