uqa_graph/
index.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Specialized graph indexes for accelerating traversal and RPQ
8//! evaluation (Section 6.4, Paper 2).
9//!
10//! `LabelIndex` exposes label cardinality and label-to-vertex sets on
11//! top of what the underlying [`GraphStore`] already tracks.
12//! `PathIndex` pre-computes the `(start, end)` reachability set for a
13//! list of label sequences so the RPQ operator can short-circuit when
14//! the input expression is a pure label-concatenation.
15
16use std::collections::{BTreeMap, BTreeSet};
17
18use uqa_core::{EdgeId, Value, VertexId};
19
20use crate::store::{GraphStore, GraphStoreError, GraphStoreResult};
21
22#[derive(Debug, Clone, Default)]
23pub struct LabelIndex {
24    label_to_edges: BTreeMap<String, Vec<EdgeId>>,
25    label_to_vertices: BTreeMap<String, BTreeSet<VertexId>>,
26}
27
28impl LabelIndex {
29    pub fn build<G: GraphStore>(store: &G, graph: &str) -> GraphStoreResult<Self> {
30        let mut idx = Self::default();
31        for vid in store.vertex_ids_in_graph(graph)? {
32            for eid in store.out_edge_ids(vid, graph)? {
33                let edge = store.get_edge(eid)?.ok_or_else(|| {
34                    GraphStoreError::CorruptGraph(format!("missing indexed edge {eid}"))
35                })?;
36                idx.label_to_edges
37                    .entry(edge.label.clone())
38                    .or_default()
39                    .push(eid);
40                let vset = idx.label_to_vertices.entry(edge.label.clone()).or_default();
41                vset.insert(edge.source_id);
42                vset.insert(edge.target_id);
43            }
44        }
45        for edges in idx.label_to_edges.values_mut() {
46            edges.sort_unstable();
47            edges.dedup();
48        }
49        Ok(idx)
50    }
51
52    pub fn edges_by_label(&self, label: &str) -> &[EdgeId] {
53        self.label_to_edges.get(label).map_or(&[], Vec::as_slice)
54    }
55
56    pub fn vertices_by_label(&self, label: &str) -> Option<&BTreeSet<VertexId>> {
57        self.label_to_vertices.get(label)
58    }
59
60    pub fn labels(&self) -> Vec<String> {
61        self.label_to_edges.keys().cloned().collect()
62    }
63
64    pub fn label_count(&self, label: &str) -> usize {
65        self.label_to_edges.get(label).map_or(0, Vec::len)
66    }
67}
68
69/// Immutable equality index over selected vertex properties in one named graph.
70///
71/// Missing properties are not indexed, while an explicitly stored
72/// [`Value::Null`] remains queryable. Value equality follows [`Value`]'s total
73/// ordering, including its cross-numeric equality rules, so indexed lookup and
74/// relational equality agree.
75#[derive(Debug, Clone, Default)]
76pub struct VertexPropertyIndex {
77    property_values: BTreeMap<String, BTreeMap<Value, BTreeSet<VertexId>>>,
78}
79
80impl VertexPropertyIndex {
81    pub fn build<G: GraphStore>(
82        store: &G,
83        graph: &str,
84        properties: &[&str],
85    ) -> GraphStoreResult<Self> {
86        let property_names: BTreeSet<String> = properties
87            .iter()
88            .map(|property| (*property).to_owned())
89            .collect();
90        let mut property_values: BTreeMap<String, BTreeMap<Value, BTreeSet<VertexId>>> =
91            property_names
92                .iter()
93                .map(|property| (property.clone(), BTreeMap::new()))
94                .collect();
95
96        for vertex_id in store.vertex_ids_in_graph(graph)? {
97            let vertex = store.get_vertex(vertex_id)?.ok_or_else(|| {
98                GraphStoreError::CorruptGraph(format!(
99                    "graph {graph:?} references missing indexed vertex {vertex_id}"
100                ))
101            })?;
102            for property in &property_names {
103                let Some(value) = vertex.properties.get(property) else {
104                    continue;
105                };
106                property_values
107                    .get_mut(property)
108                    .expect("requested property was initialized")
109                    .entry(value.clone())
110                    .or_default()
111                    .insert(vertex_id);
112            }
113        }
114
115        Ok(Self { property_values })
116    }
117
118    pub fn has_property(&self, property: &str) -> bool {
119        self.property_values.contains_key(property)
120    }
121
122    pub fn lookup_eq(&self, property: &str, value: &Value) -> Option<&BTreeSet<VertexId>> {
123        self.property_values.get(property)?.get(value)
124    }
125
126    pub fn property_names(&self) -> impl Iterator<Item = &str> {
127        self.property_values.keys().map(String::as_str)
128    }
129}
130
131// Path-index handles retain only definitions for durable stores.
132mod path_index;
133pub use path_index::PathIndex;
134
135#[cfg(test)]
136mod tests {
137    use uqa_core::{Value, Vertex};
138
139    use super::VertexPropertyIndex;
140    use crate::{GraphStore, MemoryGraphStore};
141
142    #[test]
143    fn vertex_property_index_tracks_selected_values_and_missing_fields() {
144        let mut store = MemoryGraphStore::new();
145        store.create_graph("g");
146        let mut first = Vertex::new(1, "node");
147        first.properties.insert("val".into(), Value::Int(7));
148        first.properties.insert("nullable".into(), Value::Null);
149        store.add_vertex(first, "g").unwrap();
150        let mut second = Vertex::new(2, "node");
151        second.properties.insert("val".into(), Value::Float(7.0));
152        store.add_vertex(second, "g").unwrap();
153
154        let index =
155            VertexPropertyIndex::build(&store, "g", &["val", "nullable", "missing"]).unwrap();
156
157        assert!(index.has_property("val"));
158        assert!(index.has_property("missing"));
159        assert_eq!(
160            index.lookup_eq("val", &Value::Int(7)).unwrap(),
161            &std::collections::BTreeSet::from([1, 2])
162        );
163        assert_eq!(
164            index.lookup_eq("nullable", &Value::Null).unwrap(),
165            &std::collections::BTreeSet::from([1])
166        );
167        assert!(index.lookup_eq("missing", &Value::Null).is_none());
168        assert!(index.lookup_eq("not-indexed", &Value::Int(7)).is_none());
169    }
170
171    #[test]
172    fn vertex_property_index_rejects_unknown_graph() {
173        let store = MemoryGraphStore::new();
174        let error = VertexPropertyIndex::build(&store, "missing", &["val"]).unwrap_err();
175        assert!(error.to_string().contains("missing"));
176    }
177}
uqa_graph/index.rs

uqa_graph/
index.rs
