Skip to main content

uqa_execution/
operator_tree.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Physical operator-tree execution and timing.
8//!
9//! [`PlanExecutor`] is the runtime entry point for executing an
10//! [`OperatorTree`] through a runtime driver. It records root timing
11//! statistics and produces an `EXPLAIN`-style tree string.
12
13use std::time::Instant;
14
15use uqa_core::{GeneralizedPostingList, PostingList};
16use uqa_graph::GraphPostingList;
17use uqa_operators::{DeepFusionLayer, OperatorTree};
18
19/// Statistics collected during plan execution.
20#[derive(Debug, Clone, Default)]
21pub struct ExecutionStats {
22    pub operator_name: String,
23    pub elapsed_ms: f64,
24    pub result_count: usize,
25    pub children: Vec<ExecutionStats>,
26}
27
28/// Materialised value produced by a physical [`OperatorTree`] node.
29///
30/// Most operators preserve one document id per row and therefore emit a
31/// [`PostingList`]. Graph operators retain their subgraph side table in a
32/// [`GraphPostingList`], while join operators preserve an ordered tuple of
33/// document ids in a [`GeneralizedPostingList`]. Keeping the carriers distinct
34/// prevents set operations from silently applying ordinary payload precedence
35/// to graph metadata or comparing synthetic join enumeration positions.
36#[derive(Debug, Clone, PartialEq)]
37pub enum OperatorOutput {
38    Posting(PostingList),
39    Graph(GraphPostingList),
40    Generalized(GeneralizedPostingList),
41}
42
43impl OperatorOutput {
44    #[must_use]
45    pub fn len(&self) -> usize {
46        match self {
47            Self::Posting(result) => result.len(),
48            Self::Graph(result) => result.len(),
49            Self::Generalized(result) => result.len(),
50        }
51    }
52
53    #[must_use]
54    pub fn is_empty(&self) -> bool {
55        match self {
56            Self::Posting(result) => result.is_empty(),
57            Self::Graph(result) => result.is_empty(),
58            Self::Generalized(result) => result.is_empty(),
59        }
60    }
61
62    #[must_use]
63    pub fn as_posting(&self) -> Option<&PostingList> {
64        match self {
65            Self::Posting(result) => Some(result),
66            Self::Graph(_) | Self::Generalized(_) => None,
67        }
68    }
69
70    #[must_use]
71    pub fn as_graph(&self) -> Option<&GraphPostingList> {
72        match self {
73            Self::Graph(result) => Some(result),
74            Self::Posting(_) | Self::Generalized(_) => None,
75        }
76    }
77
78    #[must_use]
79    pub fn as_generalized(&self) -> Option<&GeneralizedPostingList> {
80        match self {
81            Self::Posting(_) | Self::Graph(_) => None,
82            Self::Generalized(result) => Some(result),
83        }
84    }
85}
86
87impl From<PostingList> for OperatorOutput {
88    fn from(value: PostingList) -> Self {
89        Self::Posting(value)
90    }
91}
92
93impl From<GraphPostingList> for OperatorOutput {
94    fn from(value: GraphPostingList) -> Self {
95        Self::Graph(value)
96    }
97}
98
99impl From<GeneralizedPostingList> for OperatorOutput {
100    fn from(value: GeneralizedPostingList) -> Self {
101        Self::Generalized(value)
102    }
103}
104
105impl ExecutionStats {
106    pub fn new(name: impl Into<String>) -> Self {
107        Self {
108            operator_name: name.into(),
109            elapsed_ms: 0.0,
110            result_count: 0,
111            children: Vec::new(),
112        }
113    }
114}
115
116/// Driver that knows how to execute an [`OperatorTree`] node. The
117/// engine implements this trait (it owns the per-operator dispatch,
118/// child execution, and the runtime context); the execution-owned
119/// `PlanExecutor` only wraps root timing and stats collection.
120pub trait OperatorTreeDriver {
121    /// Failure produced by the physical runtime while materialising a
122    /// node or one of its descendants.
123    type Error;
124
125    fn execute_node(&self, op: &OperatorTree) -> Result<OperatorOutput, Self::Error>;
126}
127
128/// Executor wrapper for [`OperatorTree`].
129pub struct PlanExecutor<'d, D: OperatorTreeDriver> {
130    pub driver: &'d D,
131    last_stats: Option<ExecutionStats>,
132}
133
134impl<'d, D: OperatorTreeDriver> PlanExecutor<'d, D> {
135    pub fn new(driver: &'d D) -> Self {
136        Self {
137            driver,
138            last_stats: None,
139        }
140    }
141
142    /// Execute `op` and capture stats. Driver failures are returned to
143    /// the caller instead of being indistinguishable from an empty
144    /// physical result.
145    pub fn execute(&mut self, op: &OperatorTree) -> Result<OperatorOutput, D::Error> {
146        self.last_stats = None;
147        let start = Instant::now();
148        let result = self.driver.execute_node(op)?;
149        let mut stats = ExecutionStats::new(operator_name(op));
150        stats.elapsed_ms = start.elapsed().as_secs_f64() * 1000.0;
151        stats.result_count = result.len();
152        self.last_stats = Some(stats);
153        Ok(result)
154    }
155
156    pub fn last_stats(&self) -> Option<&ExecutionStats> {
157        self.last_stats.as_ref()
158    }
159
160    pub fn explain(&self, op: &OperatorTree) -> String {
161        let mut lines: Vec<String> = Vec::new();
162        explain_recursive(op, &mut lines, 0);
163        lines.join("\n")
164    }
165}
166
167/// Stable human-readable name for an [`OperatorTree`] variant.
168pub fn operator_name(op: &OperatorTree) -> String {
169    match op {
170        OperatorTree::Empty => "EmptyOp",
171        OperatorTree::Term {
172            top_k:
173                Some(uqa_operators::TextTopKPlan {
174                    strategy: uqa_operators::TextTopKStrategy::Wand,
175                    ..
176                }),
177            ..
178        } => "WANDTopKOp",
179        OperatorTree::Term {
180            top_k:
181                Some(uqa_operators::TextTopKPlan {
182                    strategy: uqa_operators::TextTopKStrategy::BlockMaxWand,
183                    ..
184                }),
185            ..
186        } => "BlockMaxWANDTopKOp",
187        OperatorTree::Term { .. } => "TermOp",
188        OperatorTree::Phrase { .. } => "PhraseOp",
189        OperatorTree::Filter { .. } => "FilterOp",
190        OperatorTree::Facet { .. } => "FacetOp",
191        OperatorTree::Score { .. } => "ScoreOp",
192        OperatorTree::BayesianScore { .. } => "BayesianScoreQuery",
193        OperatorTree::BayesianMatchWithPrior { .. } => "BayesianMatchWithPriorOp",
194        OperatorTree::Intersect(_) => "IntersectOp",
195        OperatorTree::Union(_) => "UnionOp",
196        OperatorTree::Complement(_) => "ComplementOp",
197        OperatorTree::Composed(_) => "ComposedOp",
198        OperatorTree::EncodeGraphPosting { .. } => "EncodeGraphPostingOp",
199        OperatorTree::VectorSimilarity { .. } => "VectorSimOp",
200        OperatorTree::KNN { .. } => "KNNOp",
201        OperatorTree::CalibratedVectorMatch { .. } => "CalibratedVectorMatchOp",
202        OperatorTree::CosineProbability(_) => "CosineProbabilityOp",
203        OperatorTree::BayesianEvidenceFusion { .. } => "BayesianEvidenceFusion",
204        OperatorTree::RobustPositiveEvidencePool { .. } => "RobustPositiveEvidencePool",
205        OperatorTree::ProbBoolFusion { .. } => "ProbBoolFusion",
206        OperatorTree::ProbNot { .. } => "ProbNot",
207        OperatorTree::AttentionFusion { .. } => "AttentionFusion",
208        OperatorTree::LearnedFusion { .. } => "LearnedFusion",
209        OperatorTree::SparseThreshold { .. } => "SparseThreshold",
210        OperatorTree::Traverse { .. } => "TraverseOp",
211        OperatorTree::GraphNeighbors { .. } => "GraphNeighborsOp",
212        OperatorTree::GraphEdges { .. } => "GraphEdgesOp",
213        OperatorTree::PatternMatch { .. } => "PatternMatchOp",
214        OperatorTree::RegularPathQuery { .. } => "RPQOp",
215        OperatorTree::GraphJoin { .. } => "GraphJoinOp",
216        OperatorTree::IndexScan { .. } => "IndexScanOp",
217        OperatorTree::Aggregate { .. } => "AggregateOp",
218        OperatorTree::GroupBy { .. } => "GroupByOp",
219        OperatorTree::MultiStage { .. } => "MultiStage",
220        OperatorTree::MultiFieldSearch { .. } => "MultiFieldSearchOp",
221        OperatorTree::HybridTextVector { .. } => "HybridTextVectorOp",
222        OperatorTree::SemanticFilter { .. } => "SemanticFilterOp",
223        OperatorTree::VectorExclusion { .. } => "VectorExclusionOp",
224        OperatorTree::FacetVector { .. } => "FacetVectorOp",
225        OperatorTree::VertexAggregation { .. } => "VertexAggregationOp",
226        OperatorTree::WeightedPathQuery { .. } => "WeightedPathQueryOp",
227        OperatorTree::MessagePassing { .. } => "MessagePassingOp",
228        OperatorTree::GraphEmbedding { .. } => "GraphEmbeddingOp",
229        OperatorTree::PageRank { .. } => "PageRankOp",
230        OperatorTree::HITS { .. } => "HITSOp",
231        OperatorTree::BetweennessCentrality { .. } => "BetweennessCentralityOp",
232        OperatorTree::TextSimilarityJoin { .. } => "TextSimilarityJoinOp",
233        OperatorTree::VectorSimilarityJoin { .. } => "VectorSimilarityJoinOp",
234        OperatorTree::HybridJoin { .. } => "HybridJoinOp",
235        OperatorTree::CrossParadigmJoin { .. } => "CrossParadigmJoinOp",
236        OperatorTree::TemporalTraverse { .. } => "TemporalTraverseOp",
237        OperatorTree::TemporalPatternMatch { .. } => "TemporalPatternMatchOp",
238        OperatorTree::ProgressiveFusion { .. } => "ProgressiveFusionOp",
239        OperatorTree::DeepFusion { .. } => "DeepFusion",
240        OperatorTree::DeepPredict { .. } => "DeepPredictOp",
241        OperatorTree::Opaque { kind, .. } => return kind.clone(),
242    }
243    .to_string()
244}
245
246#[expect(
247    clippy::too_many_lines,
248    reason = "executor exhaustively maps every operator variant and output carrier"
249)]
250fn explain_recursive(op: &OperatorTree, lines: &mut Vec<String>, indent: usize) {
251    let prefix = "  ".repeat(indent);
252    match op {
253        OperatorTree::Term {
254            query,
255            field,
256            scoring,
257            top_k,
258        } => {
259            lines.push(format!(
260                "{prefix}TermOp(term={query:?}, field={field:?}, scoring={scoring:?}, top_k={top_k:?})"
261            ));
262        }
263        OperatorTree::VectorSimilarity {
264            threshold, field, ..
265        } => {
266            lines.push(format!(
267                "{prefix}VectorSimOp(threshold={threshold}, field={field:?})"
268            ));
269        }
270        OperatorTree::KNN { k, field, .. } => {
271            lines.push(format!("{prefix}KNNOp(k={k}, field={field:?})"));
272        }
273        OperatorTree::IndexScan {
274            field, index_name, ..
275        } => {
276            lines.push(format!(
277                "{prefix}IndexScanOp(field={field:?}, index={index_name:?})"
278            ));
279        }
280        OperatorTree::Score {
281            query_terms,
282            field,
283            source,
284            ..
285        } => {
286            lines.push(format!(
287                "{prefix}ScoreOp(scorer=Scorer, terms={query_terms:?}, field={field:?})"
288            ));
289            explain_recursive(source, lines, indent + 1);
290        }
291        OperatorTree::BayesianScore { source, field } => {
292            lines.push(format!("{prefix}BayesianScoreQuery(field={field:?})"));
293            explain_recursive(source, lines, indent + 1);
294        }
295        OperatorTree::Filter { field, source, .. } => {
296            lines.push(format!("{prefix}FilterOp(field={field:?})"));
297            if let Some(src) = source {
298                explain_recursive(src, lines, indent + 1);
299            }
300        }
301        OperatorTree::BayesianEvidenceFusion { signals, base_rate } => {
302            lines.push(format!(
303                "{prefix}BayesianEvidenceFusion(base_rate={base_rate:?}, signals={})",
304                signals.len()
305            ));
306            for signal in signals {
307                explain_recursive(signal, lines, indent + 1);
308            }
309        }
310        OperatorTree::RobustPositiveEvidencePool { signals, alpha, .. } => {
311            lines.push(format!(
312                "{prefix}RobustPositiveEvidencePool(alpha={alpha}, signals={})",
313                signals.len()
314            ));
315            for sig in signals {
316                explain_recursive(sig, lines, indent + 1);
317            }
318        }
319        OperatorTree::ProbBoolFusion { signals, mode } => {
320            lines.push(format!(
321                "{prefix}ProbBoolFusion(mode={mode:?}, signals={})",
322                signals.len()
323            ));
324            for sig in signals {
325                explain_recursive(sig, lines, indent + 1);
326            }
327        }
328        OperatorTree::ProbNot { signal, .. } => {
329            lines.push(format!("{prefix}ProbNot"));
330            explain_recursive(signal, lines, indent + 1);
331        }
332        OperatorTree::AttentionFusion { signals, .. } => {
333            lines.push(format!(
334                "{prefix}AttentionFusion(signals={})",
335                signals.len()
336            ));
337            for sig in signals {
338                explain_recursive(sig, lines, indent + 1);
339            }
340        }
341        OperatorTree::LearnedFusion { signals, .. } => {
342            lines.push(format!("{prefix}LearnedFusion(signals={})", signals.len()));
343            for sig in signals {
344                explain_recursive(sig, lines, indent + 1);
345            }
346        }
347        OperatorTree::Traverse {
348            start_vertex,
349            label,
350            max_hops,
351            ..
352        } => {
353            lines.push(format!(
354                "{prefix}TraverseOp(start={start_vertex}, label={label:?}, hops={max_hops})"
355            ));
356        }
357        OperatorTree::PatternMatch { pattern, .. } => {
358            lines.push(format!(
359                "{prefix}PatternMatchOp(vertices={}, edges={})",
360                pattern.vertex_patterns.len(),
361                pattern.edge_patterns.len()
362            ));
363        }
364        OperatorTree::RegularPathQuery { start_vertex, .. } => {
365            lines.push(format!("{prefix}RPQOp(start={start_vertex})"));
366        }
367        OperatorTree::Intersect(ops) => {
368            lines.push(format!("{prefix}Intersect"));
369            for child in ops {
370                explain_recursive(child, lines, indent + 1);
371            }
372        }
373        OperatorTree::Union(ops) => {
374            lines.push(format!("{prefix}Union"));
375            for child in ops {
376                explain_recursive(child, lines, indent + 1);
377            }
378        }
379        OperatorTree::Complement(inner) => {
380            lines.push(format!("{prefix}Complement"));
381            explain_recursive(inner, lines, indent + 1);
382        }
383        OperatorTree::Composed(ops) => {
384            lines.push(format!("{prefix}Composed"));
385            for child in ops {
386                explain_recursive(child, lines, indent + 1);
387            }
388        }
389        OperatorTree::EncodeGraphPosting { source } => {
390            lines.push(format!("{prefix}EncodeGraphPosting"));
391            explain_recursive(source, lines, indent + 1);
392        }
393        OperatorTree::SparseThreshold { source, threshold } => {
394            lines.push(format!("{prefix}SparseThreshold(threshold={threshold})"));
395            explain_recursive(source, lines, indent + 1);
396        }
397        OperatorTree::MessagePassing { source } => {
398            lines.push(format!("{prefix}MessagePassingOp"));
399            explain_recursive(source, lines, indent + 1);
400        }
401        OperatorTree::GraphEmbedding { source } => {
402            lines.push(format!("{prefix}GraphEmbeddingOp"));
403            explain_recursive(source, lines, indent + 1);
404        }
405        OperatorTree::MultiStage { stages } => {
406            lines.push(format!("{prefix}MultiStage(stages={})", stages.len()));
407            for (i, entry) in stages.iter().enumerate() {
408                lines.push(format!("{prefix}  Stage {i} (cutoff={:?}):", entry.cutoff));
409                explain_recursive(&entry.child, lines, indent + 2);
410            }
411        }
412        OperatorTree::DeepFusion {
413            layers,
414            alpha,
415            gating,
416        } => {
417            lines.push(format!(
418                "{prefix}DeepFusion(layers={}, alpha={alpha}, gating={gating:?})",
419                layers.len()
420            ));
421            for (i, layer) in layers.iter().enumerate() {
422                match layer {
423                    DeepFusionLayer::Signal { signals } => {
424                        lines.push(format!("{prefix}  Layer {i} (signals={}):", signals.len()));
425                        for sig in signals {
426                            explain_recursive(sig, lines, indent + 2);
427                        }
428                    }
429                    DeepFusionLayer::Propagate {
430                        edge_label,
431                        aggregation,
432                        direction,
433                    } => {
434                        lines.push(format!(
435                            "{prefix}  Layer {i} (propagate={edge_label:?}, aggregation={aggregation:?}, direction={direction:?}):"
436                        ));
437                    }
438                    DeepFusionLayer::Conv {
439                        edge_label,
440                        hop_weights,
441                        direction,
442                    } => {
443                        lines.push(format!(
444                            "{prefix}  Layer {i} (convolve={edge_label:?}, hop_weights={hop_weights:?}, direction={direction:?}):"
445                        ));
446                    }
447                    DeepFusionLayer::Pool {
448                        edge_label,
449                        pool_size,
450                        method,
451                        direction,
452                    } => {
453                        lines.push(format!(
454                            "{prefix}  Layer {i} (pool={edge_label:?}, size={pool_size}, method={method:?}, direction={direction:?}):"
455                        ));
456                    }
457                    DeepFusionLayer::Flatten => {
458                        lines.push(format!("{prefix}  Layer {i} (flatten):"));
459                    }
460                    DeepFusionLayer::Softmax => {
461                        lines.push(format!("{prefix}  Layer {i} (softmax):"));
462                    }
463                    DeepFusionLayer::Dense {
464                        output_channels,
465                        input_channels,
466                        ..
467                    } => {
468                        lines.push(format!(
469                            "{prefix}  Layer {i} (dense, input={input_channels}, output={output_channels}):"
470                        ));
471                    }
472                    DeepFusionLayer::BatchNorm { epsilon } => {
473                        lines.push(format!(
474                            "{prefix}  Layer {i} (batch_norm, epsilon={epsilon}):"
475                        ));
476                    }
477                    DeepFusionLayer::Dropout { probability } => {
478                        lines.push(format!(
479                            "{prefix}  Layer {i} (dropout, probability={probability}):"
480                        ));
481                    }
482                }
483            }
484        }
485        OperatorTree::Opaque { kind, children, .. } => {
486            lines.push(format!("{prefix}{kind}"));
487            for child in children {
488                explain_recursive(child, lines, indent + 1);
489            }
490        }
491        other => {
492            lines.push(format!("{prefix}{}", operator_name(other)));
493        }
494    }
495}
496
497#[cfg(test)]
498mod tests {
499    use super::*;
500    use std::sync::atomic::{AtomicUsize, Ordering};
501
502    struct EmptyDriver;
503    impl OperatorTreeDriver for EmptyDriver {
504        type Error = std::convert::Infallible;
505
506        fn execute_node(&self, _op: &OperatorTree) -> Result<OperatorOutput, Self::Error> {
507            Ok(PostingList::new().into())
508        }
509    }
510
511    #[test]
512    fn explain_renders_intersect_tree() {
513        let op = OperatorTree::Intersect(vec![
514            OperatorTree::Term {
515                query: "rust".into(),
516                field: Some("body".into()),
517                scoring: None,
518                top_k: None,
519            },
520            OperatorTree::Filter {
521                field: "year".into(),
522                predicate: uqa_core::Predicate::Equals(uqa_core::Value::Int(2026)),
523                source: None,
524            },
525        ]);
526        let driver = EmptyDriver;
527        let executor = PlanExecutor::new(&driver);
528        let text = executor.explain(&op);
529        assert!(text.contains("Intersect"));
530        assert!(text.contains("TermOp"));
531        assert!(text.contains("FilterOp"));
532    }
533
534    #[test]
535    fn execute_collects_timing_stats() {
536        let op = OperatorTree::Term {
537            query: "x".into(),
538            field: Some("body".into()),
539            scoring: None,
540            top_k: None,
541        };
542        let driver = EmptyDriver;
543        let mut executor = PlanExecutor::new(&driver);
544        let _ = executor.execute(&op).expect("infallible driver");
545        let stats = executor.last_stats().expect("stats");
546        assert_eq!(stats.operator_name, "TermOp");
547        assert_eq!(stats.result_count, 0);
548        assert!(stats.elapsed_ms >= 0.0);
549    }
550
551    #[test]
552    fn execute_delegates_to_driver_once() {
553        struct CountingDriver {
554            calls: AtomicUsize,
555        }
556
557        impl OperatorTreeDriver for CountingDriver {
558            type Error = std::convert::Infallible;
559
560            fn execute_node(&self, _op: &OperatorTree) -> Result<OperatorOutput, Self::Error> {
561                self.calls.fetch_add(1, Ordering::SeqCst);
562                Ok(PostingList::new().into())
563            }
564        }
565
566        let op = OperatorTree::Intersect(vec![
567            OperatorTree::Term {
568                query: "rust".into(),
569                field: Some("body".into()),
570                scoring: None,
571                top_k: None,
572            },
573            OperatorTree::Term {
574                query: "search".into(),
575                field: Some("body".into()),
576                scoring: None,
577                top_k: None,
578            },
579        ]);
580        let driver = CountingDriver {
581            calls: AtomicUsize::new(0),
582        };
583        let mut executor = PlanExecutor::new(&driver);
584
585        let _ = executor.execute(&op).expect("infallible driver");
586
587        assert_eq!(driver.calls.load(Ordering::SeqCst), 1);
588    }
589
590    #[test]
591    fn execute_propagates_driver_errors() {
592        struct FailingDriver;
593
594        impl OperatorTreeDriver for FailingDriver {
595            type Error = &'static str;
596
597            fn execute_node(&self, _op: &OperatorTree) -> Result<OperatorOutput, Self::Error> {
598                Err("storage failure")
599            }
600        }
601
602        let driver = FailingDriver;
603        let mut executor = PlanExecutor::new(&driver);
604        let error = executor
605            .execute(&OperatorTree::Empty)
606            .expect_err("driver failure must be returned");
607
608        assert_eq!(error, "storage failure");
609        assert!(executor.last_stats().is_none());
610    }
611}
612
613pub mod driver;
614
615pub mod joins;
616pub mod query;
617pub mod runtime;
618
619pub mod binding;
620pub mod instantiate;