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            }
361            PlanDescription::with_children("Sort", d, vec![n.input])
362        }
363        PhysicalOp::Limit(n) => {
364            if let Some(skip) = &n.skip {
365                d.insert("skip".to_string(), expr_str(skip));
366            }
367            if let Some(limit) = &n.limit {
368                d.insert("limit".to_string(), expr_str(limit));
369            }
370            PlanDescription::with_children("Limit", d, vec![n.input])
371        }
372        PhysicalOp::Create(n) => {
373            d.insert(
374                "elements".to_string(),
375                pattern_summary(n.pattern.parts.len()),
376            );
377            PlanDescription::with_children("Create", d, vec![n.input])
378        }
379        PhysicalOp::Merge(n) => describe_merge(n),
380        PhysicalOp::Delete(n) => {
381            d.insert("detach".to_string(), n.detach.to_string());
382            d.insert("targets".to_string(), n.expressions.len().to_string());
383            PlanDescription::with_children("Delete", d, vec![n.input])
384        }
385        PhysicalOp::Set(n) => {
386            d.insert("items".to_string(), n.items.len().to_string());
387            PlanDescription::with_children("Set", d, vec![n.input])
388        }
389        PhysicalOp::Remove(n) => {
390            d.insert("items".to_string(), n.items.len().to_string());
391            PlanDescription::with_children("Remove", d, vec![n.input])
392        }
393        PhysicalOp::Foreach(n) => {
394            d.insert("variable".to_string(), var_str(n.variable));
395            d.insert("list".to_string(), expr_str(&n.list));
396            d.insert("body".to_string(), n.body.len().to_string());
397            PlanDescription::with_children("Foreach", d, vec![n.input])
398        }
399        PhysicalOp::OptionalMatch(n) => describe_optional_match(n),
400        PhysicalOp::CallSubquery(n) => {
401            d.insert(
402                "new_vars".to_string(),
403                n.new_vars
404                    .iter()
405                    .copied()
406                    .map(var_str)
407                    .collect::<Vec<_>>()
408                    .join(", "),
409            );
410            PlanDescription::with_children("CallSubquery", d, vec![n.input, n.inner])
411        }
412        PhysicalOp::PathBuild(n) => {
413            d.insert("output".to_string(), var_str(n.output));
414            d.insert("nodes".to_string(), n.node_vars.len().to_string());
415            d.insert("rels".to_string(), n.rel_vars.len().to_string());
416            if let Some(all) = n.shortest_path_all {
417                d.insert("shortest_path_all".to_string(), all.to_string());
418            }
419            PlanDescription::with_children("PathBuild", d, vec![n.input])
420        }
421    }
422}
423
424fn union_kind(branches: &[CompiledUnionBranch]) -> &'static str {
425    let all = branches.iter().all(|b| b.all);
426    let all_distinct = branches.iter().all(|b| !b.all);
427    if all {
428        "ALL"
429    } else if all_distinct {
430        "DISTINCT"
431    } else {
432        "MIXED"
433    }
434}
435
436fn describe_expand(n: &crate::physical::ExpandExec) -> PlanDescription {
437    let mut d = BTreeMap::new();
438    d.insert("src".to_string(), var_str(n.src));
439    d.insert("dst".to_string(), var_str(n.dst));
440    if let Some(rel) = n.rel {
441        d.insert("rel".to_string(), var_str(rel));
442    }
443    if !n.types.is_empty() {
444        d.insert("types".to_string(), n.types.join("|"));
445    }
446    d.insert(
447        "direction".to_string(),
448        direction_str(n.direction).to_string(),
449    );
450    if let Some(props) = &n.rel_properties {
451        d.insert("rel_properties".to_string(), expr_str(props));
452    }
453    if let Some(range) = &n.range {
454        d.insert("range".to_string(), format!("{:?}", range));
455    }
456    PlanDescription::with_children("Expand", d, vec![n.input])
457}
458
459fn describe_projection(n: &crate::physical::ProjectionExec) -> PlanDescription {
460    let mut d = BTreeMap::new();
461    d.insert("distinct".to_string(), n.distinct.to_string());
462    d.insert(
463        "include_existing".to_string(),
464        n.include_existing.to_string(),
465    );
466    d.insert("items".to_string(), projection_names(&n.items));
467    PlanDescription::with_children("Projection", d, vec![n.input])
468}
469
470fn describe_hash_aggregation(n: &crate::physical::HashAggregationExec) -> PlanDescription {
471    let mut d = BTreeMap::new();
472    d.insert("group_by".to_string(), projection_names(&n.group_by));
473    d.insert("aggregates".to_string(), projection_names(&n.aggregates));
474    PlanDescription::with_children("HashAggregation", d, vec![n.input])
475}
476
477fn describe_merge(n: &crate::physical::MergeExec) -> PlanDescription {
478    let mut d = BTreeMap::new();
479    d.insert("actions".to_string(), n.actions.len().to_string());
480    PlanDescription::with_children("Merge", d, vec![n.input])
481}
482
483fn describe_optional_match(n: &crate::physical::OptionalMatchExec) -> PlanDescription {
484    let mut d = BTreeMap::new();
485    d.insert(
486        "new_vars".to_string(),
487        n.new_vars
488            .iter()
489            .copied()
490            .map(var_str)
491            .collect::<Vec<_>>()
492            .join(", "),
493    );
494    PlanDescription::with_children("OptionalMatch", d, vec![n.input, n.inner])
495}
496
497fn opt_input(input: Option<PhysicalNodeId>) -> Vec<PhysicalNodeId> {
498    input.map(|i| vec![i]).unwrap_or_default()
499}
500
501fn var_str(v: lora_analyzer::symbols::VarId) -> String {
502    format!("v{}", v.0)
503}
504
505fn label_groups_str(groups: &[Vec<String>]) -> String {
506    groups
507        .iter()
508        .map(|or_group| or_group.join("|"))
509        .collect::<Vec<_>>()
510        .join("&")
511}
512
513fn projection_names(items: &[ResolvedProjection]) -> String {
514    items
515        .iter()
516        .map(|p| p.name.clone())
517        .collect::<Vec<_>>()
518        .join(", ")
519}
520
521fn direction_str(d: Direction) -> &'static str {
522    match d {
523        Direction::Right => "->",
524        Direction::Left => "<-",
525        Direction::Undirected => "-",
526    }
527}
528
529fn expr_str(e: &ResolvedExpr) -> String {
530    let mut out = String::new();
531    let _ = write!(&mut out, "{:?}", e);
532    out
533}
534
535fn pattern_summary(part_count: usize) -> String {
536    format!("{} pattern part(s)", part_count)
537}
lora_compiler/plan_tree.rs

lora_compiler/
plan_tree.rs
