uqa_planner/cardinality/
stats.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Relational, graph, and sampling statistics contracts.
8
9use super::{BTreeMap, Value, VertexConstraint};
10
11/// Jaccard-style selectivity assumed for text-similarity joins when no
12/// per-column statistics are available.
13pub const JACCARD_JOIN_SELECTIVITY: f64 = 0.05;
14
15/// Fallback average out-degree used by graph traversal cardinality
16/// when no [`GraphStats`] is supplied.
17pub const GRAPH_AVG_DEGREE_DEFAULT: f64 = 10.0;
18
19/// Physical domain used to produce one relation before relational joins.
20#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
21pub enum AccessParadigm {
22    #[default]
23    Relational,
24    Text,
25    Vector,
26    Graph,
27    Hybrid,
28    CrossParadigm,
29}
30
31/// Cardinality and work estimate for a relation-local access predicate.
32#[derive(Debug, Clone, Copy, PartialEq)]
33pub struct LocalAccessEstimate {
34    pub output_rows: f64,
35    pub cost: f64,
36    pub paradigm: AccessParadigm,
37}
38
39// ---------------------------------------------------------------------
40// Graph statistics
41// ---------------------------------------------------------------------
42
43/// Graph-level statistics for heuristic cardinality estimation.
44#[derive(Debug, Clone, Default)]
45pub struct GraphStats {
46    pub num_vertices: u64,
47    pub num_edges: u64,
48    pub label_counts: BTreeMap<String, u64>,
49    pub avg_out_degree: f64,
50    pub degree_distribution: BTreeMap<u64, u64>,
51    pub min_timestamp: Option<f64>,
52    pub max_timestamp: Option<f64>,
53    pub graph_name: String,
54    pub vertex_label_counts: BTreeMap<String, u64>,
55    pub label_degree_map: BTreeMap<String, f64>,
56}
57
58impl GraphStats {
59    /// Fraction of edges matching `label`. `None` is the wildcard label
60    /// (full edge population).
61    pub fn label_selectivity(&self, label: Option<&str>) -> f64 {
62        match label {
63            None => 1.0,
64            Some(_) if self.num_edges == 0 => 1.0,
65            Some(name) => {
66                let c = self.label_counts.get(name).copied().unwrap_or(0);
67                c as f64 / self.num_edges as f64
68            }
69        }
70    }
71
72    /// Edge density `|E| / |V|^2`.
73    pub fn edge_density(&self) -> f64 {
74        if self.num_vertices <= 1 {
75            return 0.0;
76        }
77        let nv = self.num_vertices as f64;
78        self.num_edges as f64 / (nv * nv)
79    }
80}
81
82// ---------------------------------------------------------------------
83// Random-walk sampler trait used by `_sample_graph_cardinality`.
84// ---------------------------------------------------------------------
85
86/// One outgoing edge surfaced by a [`GraphStoreSampler`].
87pub struct EdgeSample {
88    pub target_id: u64,
89    pub label: String,
90}
91
92/// Minimal graph-store interface exposing the vertex, adjacency, and edge
93/// snapshots required by the sampler.
94pub trait GraphStoreSampler: Send + Sync {
95    /// IDs of every vertex in the store.
96    fn vertex_ids(&self) -> Vec<u64>;
97
98    /// Outgoing edges from `vid`.
99    fn outgoing_edges(&self, vid: u64) -> Vec<EdgeSample>;
100
101    /// Apply a vertex-constraint callback so the sampler can keep vertex
102    /// storage behind the store implementation.
103    fn vertex_satisfies(&self, vid: u64, constraint: &VertexConstraint) -> bool;
104}
105
106// ---------------------------------------------------------------------
107// Per-column statistics (used by both AST-Expr and operator surfaces).
108// ---------------------------------------------------------------------
109
110#[derive(Debug, Clone, Default)]
111pub struct ColumnStats {
112    pub distinct_count: u64,
113    pub null_count: u64,
114    pub min_value: Option<Value>,
115    pub max_value: Option<Value>,
116    pub row_count: u64,
117    /// Equi-depth histogram bucket boundaries, sorted ascending.
118    /// `b+1` boundaries describe `b` buckets.
119    pub histogram: Vec<Value>,
120    /// Most-common values, descending by frequency.
121    pub mcv_values: Vec<Value>,
122    pub mcv_frequencies: Vec<f64>,
123}
124
125impl ColumnStats {
126    /// Default selectivity of an equality predicate over this column.
127    pub fn equality_selectivity(&self) -> f64 {
128        self.non_null_fraction() / self.distinct_count.max(1) as f64
129    }
130
131    pub fn non_null_fraction(&self) -> f64 {
132        if self.row_count == 0 {
133            1.0
134        } else {
135            (1.0 - self.null_count as f64 / self.row_count as f64).clamp(0.0, 1.0)
136        }
137    }
138
139    /// An equality constant outside the MCV list shares only its remaining probability mass.
140    pub fn equality_selectivity_for(&self, value: &Value) -> f64 {
141        if matches!(value, Value::Null) {
142            return 0.0;
143        }
144        if let Some(frequency) = self.matches_mcv(value) {
145            return frequency.clamp(0.0, 1.0);
146        }
147        let remaining =
148            (self.non_null_fraction() - self.mcv_frequencies.iter().sum::<f64>()).max(0.0);
149        let distinct = self
150            .distinct_count
151            .saturating_sub(self.mcv_values.len() as u64)
152            .max(1);
153        let selectivity = remaining / distinct as f64;
154        self.mcv_frequencies
155            .iter()
156            .copied()
157            .reduce(f64::min)
158            .map_or(selectivity, |least_common| selectivity.min(least_common))
159            .clamp(0.0, 1.0)
160    }
161
162    pub fn matches_mcv(&self, value: &Value) -> Option<f64> {
163        for (mcv, freq) in self.mcv_values.iter().zip(self.mcv_frequencies.iter()) {
164            if mcv == value {
165                return Some(*freq);
166            }
167        }
168        None
169    }
170}
171
172#[derive(Debug, Clone, Default)]
173pub struct RelationStats {
174    pub row_count: u64,
175    pub columns: BTreeMap<String, ColumnStats>,
176}
177
178impl RelationStats {
179    pub fn new(row_count: u64) -> Self {
180        Self {
181            row_count,
182            columns: BTreeMap::new(),
183        }
184    }
185
186    pub fn with_column(mut self, name: impl Into<String>, stats: ColumnStats) -> Self {
187        self.columns.insert(name.into(), stats);
188        self
189    }
190
191    pub fn column(&self, name: &str) -> Option<&ColumnStats> {
192        self.columns.get(name)
193    }
194}
195
196#[derive(Debug, Clone, Copy)]
197pub struct Selectivity(pub f64);
198
199impl Selectivity {
200    pub fn clamp(self) -> Self {
201        Self(self.0.clamp(0.0, 1.0))
202    }
203
204    pub fn raw(self) -> f64 {
205        self.0
206    }
207}
uqa_planner/cardinality/stats.rs

uqa_planner/cardinality/
stats.rs
