nodedb_graph/csr/
statistics.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! Edge table statistics for query planning and optimization.
4//!
5//! Maintains per-label edge counts and degree distribution histograms.
6//! Updated incrementally on `add_edge`/`remove_edge` and fully recomputed
7//! on `compact`. Used by the MATCH pattern compiler for join order
8//! optimization (most selective label first).
9
10use std::collections::HashMap;
11use std::mem::size_of;
12
13use nodedb_mem::EngineId;
14use serde::{Deserialize, Serialize};
15
16use super::CsrIndex;
17use crate::GraphError;
18
19/// Per-label edge statistics.
20#[derive(Debug, Clone, Serialize, Deserialize)]
21pub struct LabelStats {
22    /// Number of edges with this label.
23    pub edge_count: usize,
24    /// Number of distinct source nodes that have this label on an outbound edge.
25    pub distinct_sources: usize,
26    /// Number of distinct destination nodes that have this label on an inbound edge.
27    pub distinct_targets: usize,
28}
29
30/// Degree distribution histogram.
31#[derive(Debug, Clone, Serialize, Deserialize)]
32pub struct DegreeHistogram {
33    pub min: usize,
34    pub max: usize,
35    pub avg: f64,
36    pub p50: usize,
37    pub p95: usize,
38    pub p99: usize,
39}
40
41/// Complete graph statistics snapshot.
42#[derive(Debug, Clone, Serialize, Deserialize)]
43pub struct GraphStatistics {
44    /// Total number of nodes.
45    pub node_count: usize,
46    /// Total number of edges (all labels).
47    pub edge_count: usize,
48    /// Number of distinct edge labels.
49    pub label_count: usize,
50    /// Per-label statistics.
51    pub label_stats: HashMap<String, LabelStats>,
52    /// Out-degree distribution across all nodes.
53    pub out_degree_histogram: DegreeHistogram,
54    /// In-degree distribution across all nodes.
55    pub in_degree_histogram: DegreeHistogram,
56}
57
58impl CsrIndex {
59    /// Compute full graph statistics from the current CSR state.
60    ///
61    /// O(V + E) — iterates all nodes and edges once. Intended for query
62    /// planning, not hot-path execution.
63    ///
64    /// # Errors
65    ///
66    /// Returns [`GraphError::MemoryBudget`] if a memory governor is installed
67    /// and the degree-array working set would exceed the `Graph` engine budget.
68    pub fn compute_statistics(&self) -> Result<GraphStatistics, GraphError> {
69        let n = self.node_count();
70        if n == 0 {
71            return Ok(GraphStatistics {
72                node_count: 0,
73                edge_count: 0,
74                label_count: 0,
75                label_stats: HashMap::new(),
76                out_degree_histogram: DegreeHistogram {
77                    min: 0,
78                    max: 0,
79                    avg: 0.0,
80                    p50: 0,
81                    p95: 0,
82                    p99: 0,
83                },
84                in_degree_histogram: DegreeHistogram {
85                    min: 0,
86                    max: 0,
87                    avg: 0.0,
88                    p50: 0,
89                    p95: 0,
90                    p99: 0,
91                },
92            });
93        }
94
95        // Reserve memory for the two degree-distribution scratch arrays.
96        let degree_bytes = 2 * n * size_of::<usize>();
97        let _degree_guard = self
98            .governor
99            .as_ref()
100            .map(|g| g.reserve(EngineId::Graph, degree_bytes))
101            .transpose()?;
102
103        // Per-label counters.
104        let mut label_edge_count: HashMap<u32, usize> = HashMap::new();
105        let mut label_sources: HashMap<u32, std::collections::HashSet<u32>> = HashMap::new();
106        let mut label_targets: HashMap<u32, std::collections::HashSet<u32>> = HashMap::new();
107
108        // Degree arrays.
109        let mut out_degrees: Vec<usize> = Vec::with_capacity(n);
110        let mut in_degrees: Vec<usize> = Vec::with_capacity(n);
111
112        let mut total_edges = 0usize;
113
114        for node in 0..n {
115            let node_id = node as u32;
116            let mut out_deg = 0usize;
117            let mut in_deg = 0usize;
118
119            for (lid, dst) in self.dense_iter_out(node_id) {
120                out_deg += 1;
121                total_edges += 1;
122                *label_edge_count.entry(lid).or_insert(0) += 1;
123                label_sources.entry(lid).or_default().insert(node_id);
124                label_targets.entry(lid).or_default().insert(dst);
125            }
126
127            for (_lid, _src) in self.dense_iter_in(node_id) {
128                in_deg += 1;
129            }
130
131            out_degrees.push(out_deg);
132            in_degrees.push(in_deg);
133        }
134
135        // Build per-label stats.
136        let mut label_stats = HashMap::new();
137        for (&lid, &count) in &label_edge_count {
138            let label_name = self.label_name(lid).to_string();
139            label_stats.insert(
140                label_name,
141                LabelStats {
142                    edge_count: count,
143                    distinct_sources: label_sources.get(&lid).map_or(0, |s| s.len()),
144                    distinct_targets: label_targets.get(&lid).map_or(0, |s| s.len()),
145                },
146            );
147        }
148
149        Ok(GraphStatistics {
150            node_count: n,
151            edge_count: total_edges,
152            label_count: label_edge_count.len(),
153            label_stats,
154            out_degree_histogram: compute_histogram(&out_degrees),
155            in_degree_histogram: compute_histogram(&in_degrees),
156        })
157    }
158
159    /// Get the edge count for a specific label. O(E) unless cached.
160    ///
161    /// Returns 0 if the label doesn't exist.
162    pub fn label_edge_count(&self, label: &str) -> usize {
163        let Some(lid) = self.label_id(label) else {
164            return 0;
165        };
166
167        let n = self.node_count();
168        let mut count = 0usize;
169        for node in 0..n {
170            for (l, _dst) in self.dense_iter_out(node as u32) {
171                if l == lid {
172                    count += 1;
173                }
174            }
175        }
176        count
177    }
178
179    /// Estimate the selectivity of a label: edge_count / total_edges.
180    ///
181    /// Returns 1.0 for unknown labels (conservative — assume all edges).
182    /// Returns 0.0 for graphs with no edges.
183    pub fn label_selectivity(&self, label: &str) -> f64 {
184        let total = self.edge_count();
185        if total == 0 {
186            return 0.0;
187        }
188        let count = self.label_edge_count(label);
189        if count == 0 {
190            return 1.0; // Unknown label → conservative estimate.
191        }
192        count as f64 / total as f64
193    }
194}
195
196/// Compute degree distribution histogram from a degree array.
197fn compute_histogram(degrees: &[usize]) -> DegreeHistogram {
198    if degrees.is_empty() {
199        return DegreeHistogram {
200            min: 0,
201            max: 0,
202            avg: 0.0,
203            p50: 0,
204            p95: 0,
205            p99: 0,
206        };
207    }
208
209    let mut sorted = degrees.to_vec();
210    sorted.sort_unstable();
211
212    let n = sorted.len();
213    let sum: usize = sorted.iter().sum();
214
215    DegreeHistogram {
216        min: sorted[0],
217        max: sorted[n - 1],
218        avg: sum as f64 / n as f64,
219        p50: sorted[n / 2],
220        p95: sorted[(n as f64 * 0.95) as usize],
221        p99: sorted[((n as f64 * 0.99) as usize).min(n - 1)],
222    }
223}
224
225#[cfg(test)]
226mod tests {
227    use super::*;
228
229    #[test]
230    fn statistics_empty_graph() {
231        let csr = CsrIndex::new();
232        let stats = csr.compute_statistics().unwrap();
233        assert_eq!(stats.node_count, 0);
234        assert_eq!(stats.edge_count, 0);
235        assert_eq!(stats.label_count, 0);
236    }
237
238    #[test]
239    fn statistics_basic() {
240        let mut csr = CsrIndex::new();
241        csr.add_edge("a", "KNOWS", "b").unwrap();
242        csr.add_edge("b", "KNOWS", "c").unwrap();
243        csr.add_edge("a", "LIKES", "c").unwrap();
244        csr.compact().expect("no governor, cannot fail");
245
246        let stats = csr.compute_statistics().unwrap();
247        assert_eq!(stats.node_count, 3);
248        assert_eq!(stats.edge_count, 3);
249        assert_eq!(stats.label_count, 2);
250
251        let knows = &stats.label_stats["KNOWS"];
252        assert_eq!(knows.edge_count, 2);
253        assert_eq!(knows.distinct_sources, 2);
254        assert_eq!(knows.distinct_targets, 2);
255
256        let likes = &stats.label_stats["LIKES"];
257        assert_eq!(likes.edge_count, 1);
258    }
259
260    #[test]
261    fn degree_histogram_values() {
262        let mut csr = CsrIndex::new();
263        csr.add_edge("a", "L", "b").unwrap();
264        csr.add_edge("a", "L", "c").unwrap();
265        csr.add_edge("a", "L", "d").unwrap();
266        csr.add_edge("b", "L", "c").unwrap();
267        csr.compact().expect("no governor, cannot fail");
268
269        let stats = csr.compute_statistics().unwrap();
270        assert_eq!(stats.out_degree_histogram.min, 0);
271        assert_eq!(stats.out_degree_histogram.max, 3);
272        assert!(stats.out_degree_histogram.avg > 0.0);
273    }
274
275    #[test]
276    fn label_edge_count_direct() {
277        let mut csr = CsrIndex::new();
278        csr.add_edge("a", "KNOWS", "b").unwrap();
279        csr.add_edge("b", "KNOWS", "c").unwrap();
280        csr.add_edge("a", "LIKES", "c").unwrap();
281        csr.compact().expect("no governor, cannot fail");
282
283        assert_eq!(csr.label_edge_count("KNOWS"), 2);
284        assert_eq!(csr.label_edge_count("LIKES"), 1);
285        assert_eq!(csr.label_edge_count("NONEXISTENT"), 0);
286    }
287
288    #[test]
289    fn label_selectivity_values() {
290        let mut csr = CsrIndex::new();
291        csr.add_edge("a", "KNOWS", "b").unwrap();
292        csr.add_edge("b", "KNOWS", "c").unwrap();
293        csr.add_edge("a", "LIKES", "c").unwrap();
294        csr.compact().expect("no governor, cannot fail");
295
296        let sel_knows = csr.label_selectivity("KNOWS");
297        let sel_likes = csr.label_selectivity("LIKES");
298
299        assert!((sel_knows - 2.0 / 3.0).abs() < 1e-9);
300        assert!((sel_likes - 1.0 / 3.0).abs() < 1e-9);
301        assert_eq!(csr.label_selectivity("NONEXISTENT"), 1.0);
302    }
303
304    #[test]
305    fn statistics_serde_roundtrip() {
306        let mut csr = CsrIndex::new();
307        csr.add_edge("a", "KNOWS", "b").unwrap();
308        csr.compact().expect("no governor, cannot fail");
309
310        let stats = csr.compute_statistics().unwrap();
311        let json = sonic_rs::to_string(&stats).unwrap();
312        let parsed: GraphStatistics = sonic_rs::from_str(&json).unwrap();
313        assert_eq!(parsed.node_count, stats.node_count);
314        assert_eq!(parsed.edge_count, stats.edge_count);
315    }
316
317    #[test]
318    fn statistics_with_buffer_edges() {
319        let mut csr = CsrIndex::new();
320        csr.add_edge("a", "KNOWS", "b").unwrap();
321        // Don't compact — edges in buffer.
322        let stats = csr.compute_statistics().unwrap();
323        assert_eq!(stats.edge_count, 1);
324        assert_eq!(stats.label_stats["KNOWS"].edge_count, 1);
325    }
326}
nodedb_graph/csr/statistics.rs

nodedb_graph/csr/
statistics.rs
