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        if self.distinct_count == 0 {
129            1.0
130        } else {
131            1.0 / self.distinct_count as f64
132        }
133    }
134
135    pub fn matches_mcv(&self, value: &Value) -> Option<f64> {
136        for (mcv, freq) in self.mcv_values.iter().zip(self.mcv_frequencies.iter()) {
137            if mcv == value {
138                return Some(*freq);
139            }
140        }
141        None
142    }
143}
144
145#[derive(Debug, Clone, Default)]
146pub struct RelationStats {
147    pub row_count: u64,
148    pub columns: BTreeMap<String, ColumnStats>,
149}
150
151impl RelationStats {
152    pub fn new(row_count: u64) -> Self {
153        Self {
154            row_count,
155            columns: BTreeMap::new(),
156        }
157    }
158
159    pub fn with_column(mut self, name: impl Into<String>, stats: ColumnStats) -> Self {
160        self.columns.insert(name.into(), stats);
161        self
162    }
163
164    pub fn column(&self, name: &str) -> Option<&ColumnStats> {
165        self.columns.get(name)
166    }
167}
168
169#[derive(Debug, Clone, Copy)]
170pub struct Selectivity(pub f64);
171
172impl Selectivity {
173    pub fn clamp(self) -> Self {
174        Self(self.0.clamp(0.0, 1.0))
175    }
176
177    pub fn raw(self) -> f64 {
178        self.0
179    }
180}
uqa_planner/cardinality/stats.rs

uqa_planner/cardinality/
stats.rs
