linkrs_storage/
stats_reader.rs

1//! Column Statistics Snapshot Reader
2//!
3//! Exposes per-column storage statistics to the query optimizer as immutable
4//! snapshots. Data sources are the storage-side zone maps and persisted
5//! column stats, so reading a snapshot costs O(chunk count) rather than
6//! O(row count) and never materializes rows.
7//!
8//! The trait methods are defaulted so test stubs and partial engines only
9//! implement what they can serve; consumers must fall back conservatively
10//! when a snapshot is unavailable.
11
12use std::sync::Arc;
13
14use linkrs_core::Value;
15
16/// Immutable point-in-time statistics for one property column of a vertex
17/// tag or an edge type.
18#[derive(Debug, Clone, Default)]
19pub struct ColumnStatsSnapshot {
20    /// Live row estimate for the owning relation (tag / edge type).
21    pub row_count: u64,
22    /// Number of null values, when tracked by the storage layer.
23    pub null_count: Option<u64>,
24    /// Distinct value count excluding nulls, as an HLL union estimate over
25    /// available registers. Retained when any contributing table tracks it.
26    pub distinct_count: Option<u64>,
27    /// HLL registers backing the distinct estimate when available.
28    pub hll: Option<crate::stats::HyperLogLog>,
29    /// Global minimum over non-null values (zone-map bounds are conservative:
30    /// they only widen after writes, never shrink).
31    pub min_value: Option<Value>,
32    /// Global maximum over non-null values.
33    pub max_value: Option<Value>,
34}
35
36/// Immutable point-in-time cardinality for one vertex tag or edge type.
37///
38/// Derived from live versus allocated slot counts, so optimizers get a
39/// table-level row estimate without reassembling it from column snapshots.
40/// Counts come from shard-inconsistent reads; use them for sizing and plan
41/// costing, never as a strongly consistent census. Never persisted;
42/// recomputed per timestamp.
43#[derive(Debug, Clone, Default, PartialEq, Eq)]
44pub struct TableCardinalitySnapshot {
45    /// Live rows visible at the snapshot timestamp.
46    pub live_rows: u64,
47    /// Allocated slots including deleted-but-unreclaimed holes.
48    pub allocated_slots: u64,
49    /// Shards contributing to the counts.
50    pub shard_count: usize,
51}
52
53impl TableCardinalitySnapshot {
54    /// Deleted-but-unreclaimed slots.
55    pub fn hole_count(&self) -> u64 {
56        self.allocated_slots.saturating_sub(self.live_rows)
57    }
58
59    /// Hole rate `1 - live / allocated`, zero for empty tables.
60    pub fn hole_rate(&self) -> f64 {
61        if self.allocated_slots == 0 || self.live_rows >= self.allocated_slots {
62            0.0
63        } else {
64            1.0 - (self.live_rows as f64 / self.allocated_slots as f64)
65        }
66    }
67
68    /// Whether the snapshot carries any rows at all.
69    pub fn is_empty(&self) -> bool {
70        self.live_rows == 0 && self.allocated_slots == 0
71    }
72
73    /// Merge `other` into `self`: counts and shard counts add up, the hole
74    /// rate is always recomputed from the merged totals, never averaged.
75    pub fn absorb(&mut self, other: &TableCardinalitySnapshot) {
76        self.live_rows += other.live_rows;
77        self.allocated_slots += other.allocated_slots;
78        self.shard_count += other.shard_count;
79    }
80}
81
82impl ColumnStatsSnapshot {
83    /// Whether this snapshot carries any usable bound for selectivity
84    /// estimation.
85    pub fn has_envelope(&self) -> bool {
86        self.min_value.is_some() || self.max_value.is_some()
87    }
88
89    /// Merge `other` into `self` so that `self` covers the union of both
90    /// snapshots' rows:
91    /// - row counts add up;
92    /// - min/max bounds widen using the numeric-aware comparison shared with
93    ///   pushed-predicate evaluation;
94    /// - null counts sum over the tables that track them (missing tracking
95    ///   is treated as no contribution);
96    /// - distinct counts merge HLL registers into a union estimate when both
97    ///   sides carry HLL state; when only numeric estimates exist without
98    ///   registers the merge degrades to `None` instead of summing (a sum
99    ///   would be a loose upper bound that double-counts overlap).
100    pub fn absorb(&mut self, other: &ColumnStatsSnapshot) {
101        self.row_count += other.row_count;
102        if let Some(n) = other.null_count {
103            *self.null_count.get_or_insert(0) += n;
104        }
105        match (self.hll.clone(), other.hll.clone()) {
106            (Some(mut a), Some(b)) => {
107                a.merge(&b);
108                self.distinct_count = Some(a.estimate());
109                self.hll = Some(a);
110            }
111            (Some(a), None) => {
112                self.distinct_count = Some(a.estimate());
113                self.hll = Some(a);
114            }
115            (None, Some(b)) => {
116                self.distinct_count = Some(b.estimate());
117                self.hll = Some(b);
118            }
119            (None, None) => {
120                self.distinct_count = None;
121                self.hll = None;
122            }
123        }
124        merge_min(&mut self.min_value, other.min_value.clone());
125        merge_max(&mut self.max_value, other.max_value.clone());
126    }
127
128    /// Attach an HLL estimator and refresh the distinct estimate from it.
129    pub fn set_hll(&mut self, hll: crate::stats::HyperLogLog) {
130        self.distinct_count = Some(hll.estimate());
131        self.hll = Some(hll);
132    }
133}
134
135/// Keep the smaller of the two optional bounds, using the same numeric-aware
136/// comparison as pushed-predicate evaluation so merged envelopes stay
137/// consistent with zone-map pruning semantics.
138pub(crate) fn merge_min(cur: &mut Option<Value>, candidate: Option<Value>) {
139    let Some(v) = candidate else { return };
140    match cur {
141        Some(c)
142            if crate::vertex::column_store::compare_values(c, &v)
143                != std::cmp::Ordering::Greater => {}
144        _ => *cur = Some(v),
145    }
146}
147
148/// Keep the larger of the two optional bounds; see [`merge_min`].
149pub(crate) fn merge_max(cur: &mut Option<Value>, candidate: Option<Value>) {
150    let Some(v) = candidate else { return };
151    match cur {
152        Some(c)
153            if crate::vertex::column_store::compare_values(c, &v) != std::cmp::Ordering::Less => {}
154        _ => *cur = Some(v),
155    }
156}
157
158/// Reader capability for optimizer-facing column statistics snapshots.
159///
160/// `relation` addressing follows the catalog naming: a tag name for vertex
161/// columns and an edge type name for edge columns.
162pub trait ColumnStatsReader: Send + Sync {
163    /// Snapshot of one property column of `tag` inside `space`.
164    fn vertex_column_stats(
165        &self,
166        _space: &str,
167        _tag: &str,
168        _column: &str,
169    ) -> Option<Arc<ColumnStatsSnapshot>> {
170        None
171    }
172
173    /// Snapshot of one property column of `edge_type` inside `space`.
174    fn edge_column_stats(
175        &self,
176        _space: &str,
177        _edge_type: &str,
178        _column: &str,
179    ) -> Option<Arc<ColumnStatsSnapshot>> {
180        None
181    }
182
183    /// Table-level cardinality of vertex tag `tag` inside `space`.
184    fn vertex_table_stats(
185        &self,
186        _space: &str,
187        _tag: &str,
188    ) -> Option<Arc<TableCardinalitySnapshot>> {
189        None
190    }
191
192    /// Table-level cardinality of edge type `edge_type` inside `space`.
193    ///
194    /// Served by the engine from per-partition snapshot counts merged with
195    /// [`TableCardinalitySnapshot::absorb`]; absent only when the edge type
196    /// has no partitions. Costing falls back to live edge counts when
197    /// unavailable.
198    fn edge_table_stats(
199        &self,
200        _space: &str,
201        _edge_type: &str,
202    ) -> Option<Arc<TableCardinalitySnapshot>> {
203        None
204    }
205
206    /// Monotonic data-version stamp: changes whenever data has been written,
207    /// independent of schema changes. Used by the optimizer's statistics
208    /// cache to detect stale estimates after DML.
209    ///
210    /// Contract: `0` means "no writes observed / unknown" and is reserved;
211    /// engines backed by real data must return values that strictly increase
212    /// across DML (they may start at any value > 0). Consumers must treat a
213    /// return value of `0` as "cacheability unknown" rather than as a valid
214    /// epoch. Returns 0 when unknown.
215    fn stats_epoch(&self) -> u64 {
216        0
217    }
218}
219
220#[cfg(test)]
221mod tests {
222    use super::*;
223
224    fn snap(row_count: u64, min: Option<Value>, max: Option<Value>) -> ColumnStatsSnapshot {
225        ColumnStatsSnapshot {
226            row_count,
227            null_count: None,
228            distinct_count: None,
229            hll: None,
230            min_value: min,
231            max_value: max,
232        }
233    }
234
235    fn hll_with(values: &[i32]) -> crate::stats::HyperLogLog {
236        let mut hll = crate::stats::HyperLogLog::new();
237        for v in values {
238            hll.add_value(&Value::Int(*v));
239        }
240        hll
241    }
242
243    #[test]
244    fn absorb_widens_bounds_across_mixed_numeric_kinds() {
245        let mut acc = snap(10, Some(Value::Int(1)), Some(Value::BigInt(100)));
246        acc.null_count = Some(2);
247        acc.set_hll(hll_with(&(0..100).collect::<Vec<_>>()));
248
249        let mut other = snap(5, Some(Value::Double(-0.5)), Some(Value::SmallInt(50)));
250        other.null_count = Some(1);
251        other.set_hll(hll_with(&(100..150).collect::<Vec<_>>()));
252        acc.absorb(&other);
253
254        assert_eq!(acc.row_count, 15);
255        assert_eq!(acc.null_count, Some(3));
256        // HLL union estimate tracks the true union instead of summing.
257        let est = acc.distinct_count.unwrap() as f64;
258        assert!((est - 150.0).abs() / 150.0 < 0.2, "estimate={}", est);
259        assert_eq!(acc.min_value, Some(Value::Double(-0.5)));
260        assert_eq!(acc.max_value, Some(Value::BigInt(100)));
261    }
262
263    #[test]
264    fn absorb_drops_partial_distinct_counts() {
265        let mut acc = snap(4, None, None);
266        acc.set_hll(hll_with(&[1, 2, 3]));
267        let expected = acc.distinct_count;
268        acc.absorb(&snap(2, None, None));
269        assert_eq!(acc.distinct_count, expected);
270    }
271
272    #[test]
273    fn absorb_without_hll_registers_degrades_to_unknown() {
274        // Bare numeric estimates without registers must not be summed.
275        let mut acc = snap(4, None, None);
276        acc.distinct_count = Some(9);
277        let mut other = snap(2, None, None);
278        other.distinct_count = Some(3);
279        acc.absorb(&other);
280        assert_eq!(acc.distinct_count, None);
281    }
282
283    #[test]
284    fn absorb_keeps_null_tracking_when_only_one_side_tracks() {
285        let mut acc = snap(1, None, None);
286        acc.null_count = None;
287        let mut other = snap(1, None, None);
288        other.null_count = Some(1);
289        acc.absorb(&other);
290        assert_eq!(acc.null_count, Some(1));
291
292        // And the reverse order keeps the tracked contribution too.
293        let mut acc = snap(1, None, None);
294        acc.null_count = Some(1);
295        acc.absorb(&snap(1, None, None));
296        assert_eq!(acc.null_count, Some(1));
297    }
298
299    #[test]
300    fn merge_helpers_compare_cross_type_numerically() {
301        let mut min = Some(Value::Int(-2));
302        merge_min(&mut min, Some(Value::Double(-2.5)));
303        assert_eq!(min, Some(Value::Double(-2.5)));
304
305        let mut max = Some(Value::Float(1.5));
306        merge_max(&mut max, Some(Value::SmallInt(2)));
307        assert_eq!(max, Some(Value::SmallInt(2)));
308
309        // Non-numeric kinds fall back to native Value ordering.
310        let mut max = Some(Value::string("P99"));
311        merge_max(&mut max, Some(Value::string("P100")));
312        assert_eq!(max, Some(Value::string("P99")));
313    }
314
315    #[test]
316    fn table_cardinality_absorb_sums_and_recomputes_hole_rate() {
317        let mut acc = TableCardinalitySnapshot {
318            live_rows: 70,
319            allocated_slots: 100,
320            shard_count: 2,
321        };
322        let other = TableCardinalitySnapshot {
323            live_rows: 30,
324            allocated_slots: 50,
325            shard_count: 1,
326        };
327        acc.absorb(&other);
328        assert_eq!(acc.live_rows, 100);
329        assert_eq!(acc.allocated_slots, 150);
330        assert_eq!(acc.shard_count, 3);
331        assert_eq!(acc.hole_count(), 50);
332        let rate = acc.hole_rate();
333        assert!((rate - (1.0 - 100.0 / 150.0)).abs() < 1e-9);
334        assert!(!acc.is_empty());
335        let empty = TableCardinalitySnapshot::default();
336        assert!(empty.is_empty());
337        assert_eq!(empty.hole_rate(), 0.0);
338    }
339}
linkrs_storage/stats_reader.rs

linkrs_storage/
stats_reader.rs
