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

nodedb_graph/csr/
statistics.rs
