linkrs_query/optimizer/stats/
property.rs

1//! Attribute Statistics Information Module
2//!
3//! Provide statistical information at the attribute level, which is used by the query optimizer to estimate selectivity.
4
5use std::time::Instant;
6
7use linkrs_core::value::Value;
8
9use super::histogram::ValueHistogram;
10
11/// Property combination statistics
12///
13/// Lightweight attribute combination statistics for GROUP BY base estimation
14#[derive(Debug, Clone)]
15pub struct PropertyCombinationStats {
16    /// Property key combinations (e.g. "tag.prop1.prop2")
17    pub key: String,
18    /// Associated tags (if any)
19    pub tag_name: Option<String>,
20    /// Property List
21    pub properties: Vec<String>,
22    /// Number of joint dissimilar values
23    pub combined_distinct_values: u64,
24    /// sample size
25    pub sample_count: u64,
26    /// Last updated
27    pub last_updated: Instant,
28}
29
30impl PropertyCombinationStats {
31    /// Create new property combination statistics.
32    pub fn new(key: String, tag_name: Option<String>, properties: Vec<String>) -> Self {
33        Self {
34            key,
35            tag_name,
36            properties,
37            combined_distinct_values: 0,
38            sample_count: 0,
39            last_updated: Instant::now(),
40        }
41    }
42
43    /// Update statistics with new sample data.
44    pub fn update(&mut self, distinct_values: u64, sample_count: u64) {
45        // Use exponential moving average for stability
46        if self.sample_count == 0 {
47            self.combined_distinct_values = distinct_values;
48            self.sample_count = sample_count;
49        } else {
50            let alpha = 0.3; // Smoothing factor
51            self.combined_distinct_values = ((1.0 - alpha) * self.combined_distinct_values as f64
52                + alpha * distinct_values as f64)
53                as u64;
54            self.sample_count = self.sample_count.saturating_add(sample_count);
55        }
56        self.last_updated = Instant::now();
57    }
58
59    /// Check if statistics are stale (older than 1 hour).
60    pub fn is_stale(&self) -> bool {
61        self.last_updated.elapsed().as_secs() > 3600
62    }
63
64    /// Get the estimated cardinality.
65    pub fn estimated_cardinality(&self) -> u64 {
66        self.combined_distinct_values.max(1)
67    }
68}
69
70/// Attribute statistics information
71#[derive(Debug, Clone)]
72pub struct PropertyStatistics {
73    /// Attribute name
74    pub property_name: String,
75    /// Associated Tags (optional)
76    pub tag_name: Option<String>,
77    /// Number of different values
78    pub distinct_values: u64,
79    /// Observed minimum value in the sampled window (orderable types only).
80    pub min_value: Option<Value>,
81    /// Observed maximum value in the sampled window (orderable types only).
82    pub max_value: Option<Value>,
83    /// Optional histograms (enabled for attributes with a high cardinality)
84    pub histogram: Option<ValueHistogram>,
85    /// Is it appropriate to use a histogram? (Histograms are not necessary for attributes with a low cardinality.)
86    pub use_histogram: bool,
87    /// Null count from the storage snapshot, when tracked.
88    pub null_count: Option<u64>,
89    /// Owning relation row count from the storage snapshot, when known.
90    pub total_rows: Option<u64>,
91}
92
93impl PropertyStatistics {
94    /// Create new attribute statistics information.
95    pub fn new(property_name: String, tag_name: Option<String>) -> Self {
96        Self {
97            property_name,
98            tag_name,
99            distinct_values: 0,
100            min_value: None,
101            max_value: None,
102            histogram: None,
103            use_histogram: false,
104            null_count: None,
105            total_rows: None,
106        }
107    }
108
109    /// Setting up a histogram
110    pub fn with_histogram(mut self, histogram: ValueHistogram) -> Self {
111        self.histogram = Some(histogram);
112        self.use_histogram = true;
113        self
114    }
115
116    /// Determine whether to use a histogram.
117    pub fn should_use_histogram(&self) -> bool {
118        self.use_histogram && self.histogram.is_some()
119    }
120
121    /// Null fraction `nulls / rows` when both sides are tracked.
122    pub fn null_fraction(&self) -> Option<f64> {
123        let total = self.total_rows.filter(|&n| n > 0)?;
124        let nulls = self.null_count?;
125        Some((nulls.min(total) as f64 / total as f64).clamp(0.0, 1.0))
126    }
127
128    /// Record one observed value into the min/max envelope.
129    ///
130    /// Numeric values compare across int and float kinds with the same
131    /// numeric-aware rule as snapshot merging; string values compare
132    /// lexicographically. Mixed numeric versus string columns keep the
133    /// first-seen family. Numeric strings stay lexicographic.
134    pub fn observe_value(&mut self, value: &Value) {
135        if order_key(value).is_none() {
136            return;
137        }
138        match &self.min_value {
139            None => self.min_value = Some(value.clone()),
140            Some(cur) => {
141                if let Some(ord) = envelope_compare(value, cur) {
142                    if ord == std::cmp::Ordering::Less {
143                        self.min_value = Some(value.clone());
144                    }
145                }
146            }
147        }
148        match &self.max_value {
149            None => self.max_value = Some(value.clone()),
150            Some(cur) => {
151                if let Some(ord) = envelope_compare(value, cur) {
152                    if ord == std::cmp::Ordering::Greater {
153                        self.max_value = Some(value.clone());
154                    }
155                }
156            }
157        }
158    }
159}
160
161/// Compare envelope values with snapshot-compatible numeric semantics:
162/// exact `i64` when both sides are integers, `f64` when a float is involved,
163/// lexicographic within the string family. Returns `None` across families
164/// so mixed columns keep the first-seen family.
165fn envelope_compare(a: &Value, b: &Value) -> Option<std::cmp::Ordering> {
166    fn as_i64(value: &Value) -> Option<i64> {
167        match value {
168            Value::SmallInt(v) => Some(*v as i64),
169            Value::Int(v) => Some(*v as i64),
170            Value::BigInt(v) => Some(*v),
171            _ => None,
172        }
173    }
174    fn as_f64(value: &Value) -> Option<f64> {
175        match value {
176            Value::SmallInt(v) => Some(*v as f64),
177            Value::Int(v) => Some(*v as f64),
178            Value::BigInt(v) => Some(*v as f64),
179            Value::Float(v) => Some(*v as f64),
180            Value::Double(v) => Some(*v),
181            _ => None,
182        }
183    }
184    if let (Some(x), Some(y)) = (as_i64(a), as_i64(b)) {
185        return Some(x.cmp(&y));
186    }
187    if let (Some(x), Some(y)) = (as_f64(a), as_f64(b)) {
188        return Some(x.partial_cmp(&y).unwrap_or(std::cmp::Ordering::Equal));
189    }
190    match (a, b) {
191        (Value::String(x), Value::String(y)) => Some(x.cmp(y)),
192        (Value::FixedString(x), Value::FixedString(y)) => Some(x.cmp(y)),
193        (Value::String(x), Value::FixedString(y)) => Some(x.as_str().cmp(y.as_str())),
194        (Value::FixedString(x), Value::String(y)) => Some(x.as_str().cmp(y.as_str())),
195        _ => None,
196    }
197}
198
199/// Type-family-tagged ordering key for min/max tracking.
200///
201/// The second component orders only within one family (`i` int family,
202/// `f` float family, `s` string family).
203fn order_key(value: &Value) -> Option<(char, String)> {
204    match value {
205        Value::Null(_) => None,
206        Value::SmallInt(i) => Some(('i', format!("{:+020}", *i as i64))),
207        Value::Int(i) => Some(('i', format!("{i:+020}"))),
208        Value::BigInt(i) => Some(('i', format!("{i:+020}"))),
209        Value::Float(f) => Some(('f', ordered_bits(f.to_bits() as u64, 32))),
210        Value::Double(d) => Some(('f', ordered_bits(d.to_bits(), 64))),
211        Value::String(s) => Some(('s', s.to_string())),
212        Value::FixedString(s) => Some(('s', s.clone())),
213        _ => None,
214    }
215}
216
217/// Order-preserving hex encoding of an IEEE-754 bit pattern: sign-flipped so
218/// that lexicographic order on the encoding matches numeric order.
219fn ordered_bits(bits: u64, width: usize) -> String {
220    let flipped = if bits >> (width - 1) & 1 == 0 {
221        bits | (1 << (width - 1))
222    } else {
223        !bits
224    };
225    format!("{flipped:0width$x}", width = width / 4)
226}
227
228impl Default for PropertyStatistics {
229    fn default() -> Self {
230        Self::new(String::new(), None)
231    }
232}
233
234#[cfg(test)]
235mod tests {
236    use super::*;
237
238    #[test]
239    fn observe_value_tracks_numeric_envelope() {
240        let mut stat = PropertyStatistics::new("age".into(), Some("person".to_string()));
241        for v in [
242            Value::Int(30),
243            Value::Int(5),
244            Value::Int(42),
245            Value::Int(17),
246        ] {
247            stat.observe_value(&v);
248        }
249        assert_eq!(stat.min_value, Some(Value::Int(5)));
250        assert_eq!(stat.max_value, Some(Value::Int(42)));
251    }
252
253    #[test]
254    fn observe_value_ignores_null_and_keeps_first_family() {
255        let mut stat = PropertyStatistics::new("v".into(), None);
256        stat.observe_value(&Value::Null(linkrs_core::value::NullType::Null));
257        assert_eq!(stat.min_value, None);
258        stat.observe_value(&Value::Double(1.5));
259        // A different family does not replace an existing envelope.
260        stat.observe_value(&Value::Int(100));
261        assert_eq!(stat.min_value, Some(Value::Double(1.5)));
262    }
263
264    #[test]
265    fn observe_value_orders_strings_lexicographically() {
266        let mut stat = PropertyStatistics::new("name".into(), None);
267        for s in ["mango", "apple", "zebra"] {
268            stat.observe_value(&Value::string(s));
269        }
270        assert_eq!(stat.min_value, Some(Value::string("apple")));
271        assert_eq!(stat.max_value, Some(Value::string("zebra")));
272    }
273
274    #[test]
275    fn null_fraction_clamps_and_requires_rows() {
276        let mut stat = PropertyStatistics::new("age".into(), None);
277        assert_eq!(stat.null_fraction(), None);
278        stat.total_rows = Some(0);
279        stat.null_count = Some(0);
280        assert_eq!(stat.null_fraction(), None);
281        stat.total_rows = Some(100);
282        stat.null_count = Some(5);
283        assert_eq!(stat.null_fraction(), Some(0.05));
284        stat.null_count = Some(200);
285        assert_eq!(stat.null_fraction(), Some(1.0));
286    }
287}
linkrs_query/optimizer/stats/property.rs

linkrs_query/optimizer/stats/
property.rs
