linkrs_query/optimizer/stats/
edge.rs

1//! Border Type Statistics Module
2//!
3//! Provide statistical information at the edge type level, which is used by the query optimizer to estimate the cost of traversing the data.
4
5/// Hotspot vertex information
6#[derive(Debug, Clone)]
7pub struct HotVertexInfo {
8    /// Vertex ID
9    pub vertex_id: i64,
10    /// Out-degree
11    pub out_degree: u64,
12    /// In-degree
13    pub in_degree: u64,
14}
15
16/// Grade of inclination
17#[derive(Debug, Clone, Copy, PartialEq, Eq)]
18pub enum SkewnessLevel {
19    /// No tilt
20    None,
21    /// Slight inclination
22    Mild,
23    /// Moderate inclination
24    Moderate,
25    /// Severe tilt
26    Severe,
27}
28
29/// Edge type statistics information
30#[derive(Debug, Clone)]
31pub struct EdgeTypeStatistics {
32    /// Edge Type Name
33    pub edge_type: String,
34    /// Total number of edges
35    pub edge_count: u64,
36    /// Allocated slots including deleted-but-unreclaimed holes, when the
37    /// storage engine exposes a table cardinality snapshot. `None` means
38    /// unknown and costs fall back to the live count (zero holes).
39    pub allocated_slots: Option<u64>,
40    /// Average frequency of use
41    pub avg_out_degree: f64,
42    /// Average Indegree
43    pub avg_in_degree: f64,
44    /// Maximum Outdegree
45    pub max_out_degree: u64,
46    /// Maximum In-degree
47    pub max_in_degree: u64,
48    /// The number of unique source vertices
49    pub unique_src_vertices: u64,
50    /// Outlier standard deviation (a measure of the degree of dispersion of a distribution)
51    pub out_degree_std_dev: f64,
52    /// In-degree standard deviation
53    pub in_degree_std_dev: f64,
54    /// Gini coefficient (ranging from 0 to 1; the higher the value, the more unequal the distribution)
55    pub degree_gini_coefficient: f64,
56    /// List of the top K vertices (vertices with the highest degree)
57    pub hot_vertices: Vec<HotVertexInfo>,
58    /// Space this statistics was collected for (`None` = default).
59    pub space: Option<String>,
60    /// Schema version at collection time (used for staleness checks).
61    pub schema_version: Option<u64>,
62}
63
64impl EdgeTypeStatistics {
65    /// Create new statistical information for edge types.
66    pub fn new(edge_type: String) -> Self {
67        Self {
68            edge_type,
69            edge_count: 0,
70            allocated_slots: None,
71            avg_out_degree: 0.0,
72            avg_in_degree: 0.0,
73            max_out_degree: 0,
74            max_in_degree: 0,
75            unique_src_vertices: 0,
76            out_degree_std_dev: 0.0,
77            in_degree_std_dev: 0.0,
78            degree_gini_coefficient: 0.0,
79            hot_vertices: Vec::new(),
80            space: None,
81            schema_version: None,
82        }
83    }
84
85    /// Attach space and schema version provenance.
86    pub fn with_version(mut self, space: String, schema_version: u64) -> Self {
87        self.space = Some(space);
88        self.schema_version = Some(schema_version);
89        self
90    }
91
92    /// Estimate the cost of expansion
93    pub fn estimate_expand_cost(&self, start_nodes: u64) -> f64 {
94        start_nodes as f64 * self.avg_out_degree
95    }
96
97    /// Hole rate `1 - live / allocated`, clamped to `[0, 1)`.
98    ///
99    /// Same contract as the tag-level helper: unknown or inconsistent
100    /// snapshots report zero.
101    pub fn hole_rate(&self) -> f64 {
102        match self.allocated_slots {
103            Some(allocated)
104                if allocated > 0 && allocated > self.edge_count && self.edge_count > 0 =>
105            {
106                1.0 - (self.edge_count as f64 / allocated as f64)
107            }
108            _ => 0.0,
109        }
110    }
111
112    /// Fill the allocated slot count from a storage table snapshot.
113    /// Snapshots that carry no rows leave the field unknown.
114    pub fn apply_table_snapshot(
115        &mut self,
116        snapshot: Option<&crate::storage::stats_reader::TableCardinalitySnapshot>,
117    ) {
118        let Some(snapshot) = snapshot else {
119            return;
120        };
121        if snapshot.allocated_slots > 0 {
122            self.allocated_slots = Some(snapshot.allocated_slots);
123        }
124    }
125
126    /// Determine whether there is a significant inclination.
127    pub fn is_heavily_skewed(&self) -> bool {
128        use crate::optimizer::cost::config::{SKEW_MAX_DEGREE_RATIO, SKEW_SEVERE_GINI};
129        self.degree_gini_coefficient > SKEW_SEVERE_GINI
130            || self.max_out_degree as f64 > self.avg_out_degree * SKEW_MAX_DEGREE_RATIO
131    }
132
133    /// Obtaining the inclination level
134    pub fn skewness_level(&self) -> SkewnessLevel {
135        use crate::optimizer::cost::config::{
136            SKEW_MILD_GINI, SKEW_MODERATE_GINI, SKEW_SEVERE_GINI,
137        };
138        match self.degree_gini_coefficient {
139            g if g > SKEW_SEVERE_GINI => SkewnessLevel::Severe,
140            g if g > SKEW_MODERATE_GINI => SkewnessLevel::Moderate,
141            g if g > SKEW_MILD_GINI => SkewnessLevel::Mild,
142            _ => SkewnessLevel::None,
143        }
144    }
145
146    /// Shared skew penalty so cost and row estimation use one definition.
147    pub fn skew_penalty(&self) -> f64 {
148        use crate::optimizer::cost::config::{
149            SKEW_MILD_PENALTY, SKEW_MODERATE_PENALTY, SKEW_SEVERE_PENALTY,
150        };
151        match self.skewness_level() {
152            SkewnessLevel::Severe => SKEW_SEVERE_PENALTY,
153            SkewnessLevel::Moderate => SKEW_MODERATE_PENALTY,
154            SkewnessLevel::Mild => SKEW_MILD_PENALTY,
155            SkewnessLevel::None => 1.0,
156        }
157    }
158
159    /// Shared conservative row factor for skewed expansion.
160    pub fn skew_row_factor(&self) -> f64 {
161        use crate::optimizer::cost::config::{
162            SKEW_MILD_ROW_FACTOR, SKEW_MODERATE_ROW_FACTOR, SKEW_SEVERE_ROW_FACTOR,
163        };
164        match self.skewness_level() {
165            SkewnessLevel::Severe => SKEW_SEVERE_ROW_FACTOR,
166            SkewnessLevel::Moderate => SKEW_MODERATE_ROW_FACTOR,
167            SkewnessLevel::Mild => SKEW_MILD_ROW_FACTOR,
168            SkewnessLevel::None => 1.0,
169        }
170    }
171
172    /// Calculate the cost of tilt perception (use a more conservative estimate for tilted data)
173    pub fn calculate_skewed_expand_cost(&self, start_nodes: u64) -> f64 {
174        let base_cost = self.estimate_expand_cost(start_nodes);
175        base_cost * self.skew_penalty()
176    }
177
178    /// Determine whether it contains a hot spot vertex.
179    pub fn has_hot_vertices(&self) -> bool {
180        !self.hot_vertices.is_empty()
181    }
182
183    /// Obtain the number of hot vertices
184    pub fn hot_vertex_count(&self) -> usize {
185        self.hot_vertices.len()
186    }
187}
188
189impl Default for EdgeTypeStatistics {
190    fn default() -> Self {
191        Self::new(String::new())
192    }
193}
194
195#[cfg(test)]
196mod tests {
197    use super::*;
198
199    #[test]
200    fn hole_rate_clamps_unknown_and_inconsistent() {
201        let mut stats = EdgeTypeStatistics::new("knows".to_string());
202        assert_eq!(stats.hole_rate(), 0.0);
203
204        stats.edge_count = 1000;
205        stats.allocated_slots = Some(4000);
206        assert!((stats.hole_rate() - 0.75).abs() < 1e-9);
207
208        stats.allocated_slots = Some(10);
209        assert_eq!(stats.hole_rate(), 0.0);
210    }
211}
linkrs_query/optimizer/stats/edge.rs

linkrs_query/optimizer/stats/
edge.rs
