Skip to main content

uqa_execution/operator_tree/driver/
graph.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Graph traversal, pattern, centrality, and temporal execution.
8
9use super::{
10    graph_execution_error, graph_pattern_from_ir, numeric_score, operator_execution_error,
11    parse_rpq, require_graph_name, restrict_result_to_source, temporal_filter_from_ir, BTreeMap,
12    BTreeSet, DeepGraphDirection, DriverResult, GeneralizedPostingList, OperatorTree, Payload,
13    PhysicalRetrievalDriver, PostingEntry, PostingList, SQLError, Value, WeightedPathExecution,
14};
15
16impl PhysicalRetrievalDriver<'_> {
17    pub(super) fn execute_traverse(
18        &self,
19        start_vertex: u64,
20        graph: &str,
21        label: Option<&str>,
22        max_hops: usize,
23        vertex_predicate: Option<&uqa_operators::VertexPredicate>,
24    ) -> DriverResult<uqa_graph::GraphPostingList> {
25        let max_hops = u32::try_from(max_hops).map_err(|_| {
26            SQLError::TypeMismatch(format!("Traverse.max_hops is too large: {max_hops}"))
27        })?;
28        self.with_graph(graph, |store| {
29            let mut op = uqa_graph::Traverse::new(start_vertex, graph).max_hops(max_hops);
30            if let Some(label) = label {
31                op = op.label(label);
32            }
33            if let Some(predicate) = vertex_predicate {
34                op = op.predicate(uqa_graph::VertexPredicate::Custom(predicate.clone()));
35            }
36            op.execute(store)
37                .map_err(|error| graph_execution_error("Traverse", error))
38        })
39    }
40
41    pub(super) fn execute_graph_neighbors(
42        &self,
43        vertex: u64,
44        graph: &str,
45        label: Option<&str>,
46        direction: DeepGraphDirection,
47    ) -> DriverResult<PostingList> {
48        let direction = match direction {
49            DeepGraphDirection::Out => uqa_graph::Direction::Out,
50            DeepGraphDirection::In => uqa_graph::Direction::In,
51            DeepGraphDirection::Both => uqa_graph::Direction::Both,
52        };
53        let neighbors = self.with_graph(graph, |store| {
54            <uqa_graph::GraphStoreHandle as uqa_graph::GraphStore>::neighbors(
55                store, vertex, label, direction, graph,
56            )
57            .map_err(|error| graph_execution_error("GraphNeighbors", error))
58        })?;
59        let entries = neighbors
60            .into_iter()
61            .collect::<BTreeSet<_>>()
62            .into_iter()
63            .map(|doc_id| {
64                PostingEntry::new(
65                    doc_id,
66                    Payload {
67                        score: 1.0,
68                        ..Default::default()
69                    },
70                )
71            })
72            .collect();
73        Ok(PostingList::from_sorted_unchecked(entries))
74    }
75
76    pub(super) fn execute_graph_edges(
77        &self,
78        graph: &str,
79        label: Option<&str>,
80    ) -> DriverResult<PostingList> {
81        let edges = self.with_graph(graph, |store| {
82            use uqa_graph::GraphStore as _;
83            match label {
84                Some(label) => store.edges_by_label(label, graph),
85                None => store.edges_in_graph(graph),
86            }
87            .map_err(|error| graph_execution_error("GraphEdges", error))
88        })?;
89        let mut entries = Vec::new();
90        for edge in edges {
91            let score = match edge.properties.get("weight") {
92                Some(Value::Float(value)) => *value,
93                Some(Value::Int(value)) => *value as f64,
94                Some(Value::Decimal(value)) => value.to_f64().ok_or_else(|| {
95                    SQLError::TypeMismatch("GraphEdges.weight decimal is outside f64 range".into())
96                })?,
97                _ => 1.0,
98            };
99            entries.push(PostingEntry::new(
100                edge.edge_id,
101                Payload {
102                    score,
103                    ..Default::default()
104                },
105            ));
106        }
107        Ok(PostingList::from_unsorted(entries))
108    }
109
110    pub(super) fn execute_pattern_match(
111        &self,
112        pattern: &uqa_operators::GraphPatternIR,
113        graph: &str,
114    ) -> DriverResult<uqa_graph::GraphPostingList> {
115        let pattern = graph_pattern_from_ir(pattern);
116        self.with_graph(graph, |store| {
117            uqa_graph::GMatch::new(pattern, graph)
118                .execute(store)
119                .map_err(|error| graph_execution_error("PatternMatch", error))
120        })
121    }
122
123    pub(super) fn execute_regular_path_query(
124        &self,
125        rpq_source: &str,
126        start_vertex: u64,
127        graph: &str,
128    ) -> DriverResult<uqa_graph::GraphPostingList> {
129        let path = parse_rpq(rpq_source)?;
130        self.with_graph(graph, |store| {
131            uqa_graph::RegularPathQuery::new(path, graph)
132                .from_vertex(start_vertex)
133                .execute(store)
134                .map_err(|error| graph_execution_error("RegularPathQuery", error))
135        })
136    }
137
138    pub(super) fn execute_graph_join(
139        &self,
140        left: &OperatorTree,
141        right: &OperatorTree,
142        label: Option<&str>,
143        graph: &str,
144    ) -> DriverResult<GeneralizedPostingList> {
145        let left = self.execute_posting_node(left)?;
146        let right = self.execute_posting_node(right)?;
147        self.join_graph_postings(&left, &right, label, graph)
148    }
149
150    pub fn join_graph_postings(
151        &self,
152        left: &PostingList,
153        right: &PostingList,
154        label: Option<&str>,
155        graph: &str,
156    ) -> DriverResult<GeneralizedPostingList> {
157        self.with_graph(graph, |store| {
158            let mut op = uqa_joins::GraphJoin::new(left.entries(), right.entries(), store, graph);
159            if let Some(label) = label {
160                op = op.label(label);
161            }
162            op.execute()
163                .map_err(|error| graph_execution_error("GraphJoin", error))
164        })
165    }
166
167    pub(super) fn execute_vertex_aggregation(
168        &self,
169        source: &OperatorTree,
170        monoid: &std::sync::Arc<dyn uqa_operators::AggregationMonoid>,
171    ) -> DriverResult<PostingList> {
172        let source = self.execute_posting_node(source)?;
173        let mut state = monoid.identity();
174        for entry in source.entries() {
175            state = monoid
176                .accumulate(state, &Value::Float(entry.payload.score))
177                .map_err(|error| operator_execution_error("VertexAggregation", error))?;
178        }
179        let result = monoid
180            .finalize(state)
181            .map_err(|error| operator_execution_error("VertexAggregation", error))?;
182        let score = numeric_score(&result);
183        let mut fields = BTreeMap::new();
184        fields.insert("_vertex_aggregate".to_string(), result);
185        fields.insert(
186            "_vertex_aggregate_count".to_string(),
187            Value::Int(i64::try_from(source.len()).map_err(|_| {
188                SQLError::Internal(format!(
189                    "vertex aggregate input count {} exceeds the SQL BIGINT range",
190                    source.len()
191                ))
192            })?),
193        );
194        Ok(PostingList::from_sorted_unchecked(vec![PostingEntry::new(
195            0,
196            Payload {
197                score,
198                fields,
199                ..Default::default()
200            },
201        )]))
202    }
203
204    pub(super) fn execute_weighted_path_query(
205        &self,
206        query: WeightedPathExecution<'_>,
207    ) -> DriverResult<uqa_graph::GraphPostingList> {
208        let WeightedPathExecution {
209            rpq_source,
210            start_vertex,
211            graph,
212            weight_property,
213            default_edge_weight,
214            max_hops,
215            predicate,
216            predicate_selectivity,
217            score,
218        } = query;
219        if !predicate_selectivity.is_finite() || !(0.0..=1.0).contains(&predicate_selectivity) {
220            return Err(SQLError::TypeMismatch(format!(
221                "WeightedPathQuery.predicate_selectivity must be finite and in [0, 1], got {predicate_selectivity}"
222            )));
223        }
224        if weight_property.is_empty() {
225            return Err(SQLError::TypeMismatch(
226                "WeightedPathQuery.weight_property must not be empty".to_string(),
227            ));
228        }
229        if !default_edge_weight.is_finite() {
230            return Err(SQLError::TypeMismatch(format!(
231                "WeightedPathQuery.default_edge_weight must be finite, got {default_edge_weight}"
232            )));
233        }
234        if !score.is_finite() {
235            return Err(SQLError::TypeMismatch(format!(
236                "WeightedPathQuery.score must be finite, got {score}"
237            )));
238        }
239        let path = parse_rpq(rpq_source)?;
240        self.with_graph(graph, |store| {
241            let mut op = uqa_graph::WeightedPathQuery::new(
242                path,
243                graph,
244                weight_property,
245                std::sync::Arc::clone(predicate),
246            )
247            .from_vertex(start_vertex);
248            op.default_edge_weight = default_edge_weight;
249            op.max_hops = max_hops;
250            op.score = score;
251            op.execute(store)
252                .map_err(|error| graph_execution_error("WeightedPathQuery", error))
253        })
254    }
255
256    pub(super) fn execute_message_passing(
257        &self,
258        source: &OperatorTree,
259    ) -> DriverResult<uqa_graph::GraphPostingList> {
260        let graph = require_graph_name(source, "MessagePassing.source")?;
261        let source_result = self.execute_posting_node(source)?;
262        let result = self.with_graph(&graph, |store| {
263            uqa_graph::MessagePassing::new(&graph)
264                .execute(store)
265                .map_err(|error| graph_execution_error("MessagePassing", error))
266        })?;
267        Ok(uqa_graph::GraphPostingList::from_posting_list(
268            &restrict_result_to_source(&result.to_posting_list(), &source_result),
269        ))
270    }
271
272    pub(super) fn execute_graph_embedding(
273        &self,
274        source: &OperatorTree,
275    ) -> DriverResult<uqa_graph::GraphPostingList> {
276        let graph = require_graph_name(source, "GraphEmbedding.source")?;
277        let source_result = self.execute_posting_node(source)?;
278        let result = self.with_graph(&graph, |store| {
279            uqa_graph::GraphEmbedding::new(&graph)
280                .execute(store)
281                .map_err(|error| graph_execution_error("GraphEmbedding", error))
282        })?;
283        Ok(uqa_graph::GraphPostingList::from_posting_list(
284            &restrict_result_to_source(&result.to_posting_list(), &source_result),
285        ))
286    }
287
288    pub(super) fn execute_page_rank(
289        &self,
290        graph: &str,
291    ) -> DriverResult<uqa_graph::GraphPostingList> {
292        self.with_graph(graph, |store| {
293            uqa_graph::PageRank::new(graph)
294                .execute(store)
295                .map_err(|error| graph_execution_error("PageRank", error))
296        })
297    }
298
299    pub(super) fn execute_hits(&self, graph: &str) -> DriverResult<uqa_graph::GraphPostingList> {
300        self.with_graph(graph, |store| {
301            uqa_graph::HITS::new(graph)
302                .execute(store)
303                .map_err(|error| graph_execution_error("HITS", error))
304        })
305    }
306
307    pub(super) fn execute_betweenness_centrality(
308        &self,
309        graph: &str,
310    ) -> DriverResult<uqa_graph::GraphPostingList> {
311        self.with_graph(graph, |store| {
312            uqa_graph::BetweennessCentrality::new(graph)
313                .execute(store)
314                .map_err(|error| graph_execution_error("BetweennessCentrality", error))
315        })
316    }
317
318    pub(super) fn execute_temporal_traverse(
319        &self,
320        start_vertex: u64,
321        graph: &str,
322        label: Option<&str>,
323        max_hops: usize,
324        temporal_filter: Option<&uqa_operators::TemporalFilterIR>,
325    ) -> DriverResult<uqa_graph::GraphPostingList> {
326        let max_hops = u32::try_from(max_hops).map_err(|_| {
327            SQLError::TypeMismatch(format!(
328                "TemporalTraverse.max_hops is too large: {max_hops}"
329            ))
330        })?;
331        let filter = temporal_filter_from_ir(temporal_filter)?;
332        self.with_graph(graph, |store| {
333            let mut op = uqa_graph::TemporalTraverse::new(start_vertex, graph)
334                .max_hops(max_hops)
335                .filter(filter);
336            if let Some(label) = label {
337                op = op.label(label);
338            }
339            op.execute(store)
340                .map_err(|error| graph_execution_error("TemporalTraverse", error))
341        })
342    }
343
344    pub(super) fn execute_temporal_pattern_match(
345        &self,
346        pattern: &uqa_operators::GraphPatternIR,
347        graph: &str,
348        temporal_filter: Option<&uqa_operators::TemporalFilterIR>,
349    ) -> DriverResult<uqa_graph::GraphPostingList> {
350        let pattern = graph_pattern_from_ir(pattern);
351        let filter = temporal_filter_from_ir(temporal_filter)?;
352        self.with_graph(graph, |store| {
353            uqa_graph::TemporalPatternMatch::new(pattern, graph)
354                .filter(filter)
355                .execute(store)
356                .map_err(|error| graph_execution_error("TemporalPatternMatch", error))
357        })
358    }
359
360    pub(super) fn with_graph<R>(
361        &self,
362        graph: &str,
363        execute: impl FnOnce(&uqa_graph::GraphStoreHandle) -> DriverResult<R>,
364    ) -> DriverResult<R> {
365        execute(self.graph_handle(graph)?.as_ref())
366    }
367
368    pub(super) fn graph_handle(
369        &self,
370        graph: &str,
371    ) -> DriverResult<std::sync::Arc<uqa_graph::GraphStoreHandle>> {
372        self.context
373            .graphs
374            .graph_handle(graph)?
375            .ok_or_else(|| SQLError::Unsupported(format!("unknown graph {graph:?}")))
376    }
377}