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            if n.in_list {
157                d.insert("mode".to_string(), "in".to_string());
158            }
159            PlanDescription::with_children("NodeByPropertyScan", d, opt_input(n.input))
160        }
161        PhysicalOp::NodeByPropertyRangeScan(n) => {
162            d.insert("var".to_string(), var_str(n.var));
163            if !n.labels.is_empty() {
164                d.insert("labels".to_string(), label_groups_str(&n.labels));
165            }
166            d.insert("key".to_string(), n.key.clone());
167            if let Some(lo) = &n.lo {
168                d.insert(
169                    "lo".to_string(),
170                    format!(
171                        "{} {}",
172                        if n.lo_inclusive { ">=" } else { ">" },
173                        expr_str(lo)
174                    ),
175                );
176            }
177            if let Some(hi) = &n.hi {
178                d.insert(
179                    "hi".to_string(),
180                    format!(
181                        "{} {}",
182                        if n.hi_inclusive { "<=" } else { "<" },
183                        expr_str(hi)
184                    ),
185                );
186            }
187            PlanDescription::with_children("NodeByPropertyRangeScan", d, opt_input(n.input))
188        }
189        PhysicalOp::NodeByPointScan(n) => {
190            d.insert("var".to_string(), var_str(n.var));
191            if !n.labels.is_empty() {
192                d.insert("labels".to_string(), label_groups_str(&n.labels));
193            }
194            d.insert("key".to_string(), n.key.clone());
195            match &n.predicate {
196                crate::PointPredicate::WithinBBox {
197                    lower_left,
198                    upper_right,
199                } => {
200                    d.insert("predicate".to_string(), "withinBBox".to_string());
201                    d.insert("lowerLeft".to_string(), expr_str(lower_left));
202                    d.insert("upperRight".to_string(), expr_str(upper_right));
203                }
204                crate::PointPredicate::WithinDistance {
205                    center,
206                    max_distance,
207                    inclusive,
208                } => {
209                    d.insert(
210                        "predicate".to_string(),
211                        if *inclusive {
212                            "distance<="
213                        } else {
214                            "distance<"
215                        }
216                        .to_string(),
217                    );
218                    d.insert("center".to_string(), expr_str(center));
219                    d.insert("maxDistance".to_string(), expr_str(max_distance));
220                }
221            }
222            PlanDescription::with_children("NodeByPointScan", d, opt_input(n.input))
223        }
224        PhysicalOp::NodeByTextScan(n) => {
225            d.insert("var".to_string(), var_str(n.var));
226            if !n.labels.is_empty() {
227                d.insert("labels".to_string(), label_groups_str(&n.labels));
228            }
229            d.insert("key".to_string(), n.key.clone());
230            d.insert(
231                "predicate".to_string(),
232                match n.predicate {
233                    crate::TextPredicate::StartsWith => "STARTS WITH",
234                    crate::TextPredicate::EndsWith => "ENDS WITH",
235                    crate::TextPredicate::Contains => "CONTAINS",
236                }
237                .to_string(),
238            );
239            d.insert("query".to_string(), expr_str(&n.query));
240            PlanDescription::with_children("NodeByTextScan", d, opt_input(n.input))
241        }
242        PhysicalOp::RelByPropertyRangeScan(n) => {
243            d.insert("rel".to_string(), var_str(n.rel));
244            d.insert("src".to_string(), var_str(n.src));
245            d.insert("dst".to_string(), var_str(n.dst));
246            if !n.types.is_empty() {
247                d.insert("types".to_string(), n.types.join("|"));
248            }
249            d.insert(
250                "direction".to_string(),
251                direction_str(n.direction).to_string(),
252            );
253            d.insert("key".to_string(), n.key.clone());
254            if let Some(lo) = &n.lo {
255                d.insert(
256                    "lo".to_string(),
257                    format!(
258                        "{} {}",
259                        if n.lo_inclusive { ">=" } else { ">" },
260                        expr_str(lo)
261                    ),
262                );
263            }
264            if let Some(hi) = &n.hi {
265                d.insert(
266                    "hi".to_string(),
267                    format!(
268                        "{} {}",
269                        if n.hi_inclusive { "<=" } else { "<" },
270                        expr_str(hi)
271                    ),
272                );
273            }
274            PlanDescription::with_children("RelByPropertyRangeScan", d, opt_input(n.input))
275        }
276        PhysicalOp::RelByTextScan(n) => {
277            d.insert("rel".to_string(), var_str(n.rel));
278            d.insert("src".to_string(), var_str(n.src));
279            d.insert("dst".to_string(), var_str(n.dst));
280            if !n.types.is_empty() {
281                d.insert("types".to_string(), n.types.join("|"));
282            }
283            d.insert(
284                "direction".to_string(),
285                direction_str(n.direction).to_string(),
286            );
287            d.insert("key".to_string(), n.key.clone());
288            d.insert(
289                "predicate".to_string(),
290                match n.predicate {
291                    crate::TextPredicate::StartsWith => "STARTS WITH",
292                    crate::TextPredicate::EndsWith => "ENDS WITH",
293                    crate::TextPredicate::Contains => "CONTAINS",
294                }
295                .to_string(),
296            );
297            d.insert("query".to_string(), expr_str(&n.query));
298            PlanDescription::with_children("RelByTextScan", d, opt_input(n.input))
299        }
300        PhysicalOp::RelByPointScan(n) => {
301            d.insert("rel".to_string(), var_str(n.rel));
302            d.insert("src".to_string(), var_str(n.src));
303            d.insert("dst".to_string(), var_str(n.dst));
304            if !n.types.is_empty() {
305                d.insert("types".to_string(), n.types.join("|"));
306            }
307            d.insert(
308                "direction".to_string(),
309                direction_str(n.direction).to_string(),
310            );
311            d.insert("key".to_string(), n.key.clone());
312            match &n.predicate {
313                crate::PointPredicate::WithinBBox {
314                    lower_left,
315                    upper_right,
316                } => {
317                    d.insert("predicate".to_string(), "withinBBox".to_string());
318                    d.insert("lowerLeft".to_string(), expr_str(lower_left));
319                    d.insert("upperRight".to_string(), expr_str(upper_right));
320                }
321                crate::PointPredicate::WithinDistance {
322                    center,
323                    max_distance,
324                    inclusive,
325                } => {
326                    d.insert(
327                        "predicate".to_string(),
328                        if *inclusive {
329                            "distance<="
330                        } else {
331                            "distance<"
332                        }
333                        .to_string(),
334                    );
335                    d.insert("center".to_string(), expr_str(center));
336                    d.insert("maxDistance".to_string(), expr_str(max_distance));
337                }
338            }
339            PlanDescription::with_children("RelByPointScan", d, opt_input(n.input))
340        }
341        PhysicalOp::Expand(n) => describe_expand(n),
342        PhysicalOp::Filter(n) => {
343            d.insert("predicate".to_string(), expr_str(&n.predicate));
344            PlanDescription::with_children("Filter", d, vec![n.input])
345        }
346        PhysicalOp::Projection(n) => describe_projection(n),
347        PhysicalOp::Unwind(n) => {
348            d.insert("alias".to_string(), var_str(n.alias));
349            d.insert("expr".to_string(), expr_str(&n.expr));
350            PlanDescription::with_children("Unwind", d, vec![n.input])
351        }
352        PhysicalOp::HashAggregation(n) => describe_hash_aggregation(n),
353        PhysicalOp::Sort(n) => {
354            d.insert(
355                "items".to_string(),
356                format!("{} sort key(s)", n.items.len()),
357            );
358            if let Some(top_k) = n.top_k {
359                d.insert("top_k".to_string(), top_k.to_string());
360            } else if let Some(bound) = &n.limit {
361                let limit = expr_str(&bound.limit);
362                let top_k = match &bound.skip {
363                    Some(skip) => format!("{} + {limit}", expr_str(skip)),
364                    None => limit,
365                };
366                d.insert("top_k".to_string(), top_k);
367            }
368            PlanDescription::with_children("Sort", d, vec![n.input])
369        }
370        PhysicalOp::Limit(n) => {
371            if let Some(skip) = &n.skip {
372                d.insert("skip".to_string(), expr_str(skip));
373            }
374            if let Some(limit) = &n.limit {
375                d.insert("limit".to_string(), expr_str(limit));
376            }
377            PlanDescription::with_children("Limit", d, vec![n.input])
378        }
379        PhysicalOp::Create(n) => {
380            d.insert(
381                "elements".to_string(),
382                pattern_summary(n.pattern.parts.len()),
383            );
384            PlanDescription::with_children("Create", d, vec![n.input])
385        }
386        PhysicalOp::Merge(n) => describe_merge(n),
387        PhysicalOp::Delete(n) => {
388            d.insert("detach".to_string(), n.detach.to_string());
389            d.insert("targets".to_string(), n.expressions.len().to_string());
390            PlanDescription::with_children("Delete", d, vec![n.input])
391        }
392        PhysicalOp::Set(n) => {
393            d.insert("items".to_string(), n.items.len().to_string());
394            PlanDescription::with_children("Set", d, vec![n.input])
395        }
396        PhysicalOp::Remove(n) => {
397            d.insert("items".to_string(), n.items.len().to_string());
398            PlanDescription::with_children("Remove", d, vec![n.input])
399        }
400        PhysicalOp::Foreach(n) => {
401            d.insert("variable".to_string(), var_str(n.variable));
402            d.insert("list".to_string(), expr_str(&n.list));
403            d.insert("body".to_string(), n.body.len().to_string());
404            PlanDescription::with_children("Foreach", d, vec![n.input])
405        }
406        PhysicalOp::OptionalMatch(n) => describe_optional_match(n),
407        PhysicalOp::CallSubquery(n) => {
408            d.insert(
409                "new_vars".to_string(),
410                n.new_vars
411                    .iter()
412                    .copied()
413                    .map(var_str)
414                    .collect::<Vec<_>>()
415                    .join(", "),
416            );
417            PlanDescription::with_children("CallSubquery", d, vec![n.input, n.inner])
418        }
419        PhysicalOp::PathBuild(n) => {
420            d.insert("output".to_string(), var_str(n.output));
421            d.insert("nodes".to_string(), n.node_vars.len().to_string());
422            d.insert("rels".to_string(), n.rel_vars.len().to_string());
423            if let Some(all) = n.shortest_path_all {
424                d.insert("shortest_path_all".to_string(), all.to_string());
425            }
426            PlanDescription::with_children("PathBuild", d, vec![n.input])
427        }
428    }
429}
430
431fn union_kind(branches: &[CompiledUnionBranch]) -> &'static str {
432    let all = branches.iter().all(|b| b.all);
433    let all_distinct = branches.iter().all(|b| !b.all);
434    if all {
435        "ALL"
436    } else if all_distinct {
437        "DISTINCT"
438    } else {
439        "MIXED"
440    }
441}
442
443fn describe_expand(n: &crate::physical::ExpandExec) -> PlanDescription {
444    let mut d = BTreeMap::new();
445    d.insert("src".to_string(), var_str(n.src));
446    d.insert("dst".to_string(), var_str(n.dst));
447    if let Some(rel) = n.rel {
448        d.insert("rel".to_string(), var_str(rel));
449    }
450    if !n.types.is_empty() {
451        d.insert("types".to_string(), n.types.join("|"));
452    }
453    d.insert(
454        "direction".to_string(),
455        direction_str(n.direction).to_string(),
456    );
457    if let Some(props) = &n.rel_properties {
458        d.insert("rel_properties".to_string(), expr_str(props));
459    }
460    if let Some(range) = &n.range {
461        d.insert("range".to_string(), format!("{:?}", range));
462    }
463    PlanDescription::with_children("Expand", d, vec![n.input])
464}
465
466fn describe_projection(n: &crate::physical::ProjectionExec) -> PlanDescription {
467    let mut d = BTreeMap::new();
468    d.insert("distinct".to_string(), n.distinct.to_string());
469    d.insert(
470        "include_existing".to_string(),
471        n.include_existing.to_string(),
472    );
473    d.insert("items".to_string(), projection_names(&n.items));
474    PlanDescription::with_children("Projection", d, vec![n.input])
475}
476
477fn describe_hash_aggregation(n: &crate::physical::HashAggregationExec) -> PlanDescription {
478    let mut d = BTreeMap::new();
479    d.insert("group_by".to_string(), projection_names(&n.group_by));
480    d.insert("aggregates".to_string(), projection_names(&n.aggregates));
481    PlanDescription::with_children("HashAggregation", d, vec![n.input])
482}
483
484fn describe_merge(n: &crate::physical::MergeExec) -> PlanDescription {
485    let mut d = BTreeMap::new();
486    d.insert("actions".to_string(), n.actions.len().to_string());
487    PlanDescription::with_children("Merge", d, vec![n.input])
488}
489
490fn describe_optional_match(n: &crate::physical::OptionalMatchExec) -> PlanDescription {
491    let mut d = BTreeMap::new();
492    d.insert(
493        "new_vars".to_string(),
494        n.new_vars
495            .iter()
496            .copied()
497            .map(var_str)
498            .collect::<Vec<_>>()
499            .join(", "),
500    );
501    PlanDescription::with_children("OptionalMatch", d, vec![n.input, n.inner])
502}
503
504fn opt_input(input: Option<PhysicalNodeId>) -> Vec<PhysicalNodeId> {
505    input.map(|i| vec![i]).unwrap_or_default()
506}
507
508fn var_str(v: lora_analyzer::symbols::VarId) -> String {
509    format!("v{}", v.0)
510}
511
512fn label_groups_str(groups: &[Vec<String>]) -> String {
513    groups
514        .iter()
515        .map(|or_group| or_group.join("|"))
516        .collect::<Vec<_>>()
517        .join("&")
518}
519
520fn projection_names(items: &[ResolvedProjection]) -> String {
521    items
522        .iter()
523        .map(|p| p.name.clone())
524        .collect::<Vec<_>>()
525        .join(", ")
526}
527
528fn direction_str(d: Direction) -> &'static str {
529    match d {
530        Direction::Right => "->",
531        Direction::Left => "<-",
532        Direction::Undirected => "-",
533    }
534}
535
536fn expr_str(e: &ResolvedExpr) -> String {
537    let mut out = String::new();
538    let _ = write!(&mut out, "{:?}", e);
539    out
540}
541
542fn pattern_summary(part_count: usize) -> String {
543    format!("{} pattern part(s)", part_count)
544}
lora_compiler/plan_tree.rs

lora_compiler/
plan_tree.rs
