lora_store/memory/
stats.rs

1//! Lightweight cardinality stats used by the cost model.
2//!
3//! Label and type counts are exact, derived in O(labels + types) from
4//! the existing `nodes_by_label` / `relationships_by_type` maps. The
5//! per-(label / type, property) distinct counts are estimates from the
6//! counting multi-resolution bitmaps in `memory::distinct_stats`, kept
7//! for every property key on every write (deletes included) and
8//! rebuilt on snapshot load / WAL replay. No separate ANALYZE phase, no
9//! background sampling, and no dependence on which hash property indexes
10//! happen to be active.
11
12use std::collections::{hash_map::DefaultHasher, BTreeMap, BTreeSet};
13use std::hash::{Hash, Hasher};
14use std::sync::Arc;
15
16/// `(label or relationship type, property key) → estimated distinct
17/// values`.
18pub type DistinctValues = BTreeMap<(String, String), usize>;
19
20/// Snapshot of graph cardinality. Populated by the storage backend
21/// (see [`super::InMemoryGraph::stats`]).
22#[derive(Debug, Default, Clone, PartialEq, Eq)]
23pub struct GraphStats {
24    /// Total live node count.
25    pub node_count: usize,
26    /// Total live relationship count.
27    pub relationship_count: usize,
28    /// Per-label node count. `nodes_by_label[label].len()`.
29    pub nodes_by_label: BTreeMap<String, usize>,
30    /// Per-rel-type relationship count. `relationships_by_type[type].len()`.
31    pub relationships_by_type: BTreeMap<String, usize>,
32    /// Per-(label, property) approximate distinct value count, for
33    /// every property key that a live node with that label carries,
34    /// indexed or not. Estimated from a distinct-value sketch kept on
35    /// every write (see `memory::distinct_stats`): a function of the live
36    /// data alone, so a restarted process, the writer and a process with
37    /// a different lookup history get the same numbers. Absent only for
38    /// keys no node of the label has (or whose values the hash index
39    /// can't key: NaN, durations, points, vectors). Shared: the store
40    /// reuses one map while the estimates don't change.
41    pub node_distinct_values: Arc<DistinctValues>,
42    /// Per-(relationship type, property) distinct value count; as above.
43    pub relationship_distinct_values: Arc<DistinctValues>,
44    /// Online catalog-backed range indexes by `(label_or_type, property)`.
45    pub node_range_indexes: BTreeSet<(String, String)>,
46    pub relationship_range_indexes: BTreeSet<(String, String)>,
47    /// Online catalog-backed text indexes by `(label_or_type, property)`.
48    pub node_text_indexes: BTreeSet<(String, String)>,
49    pub relationship_text_indexes: BTreeSet<(String, String)>,
50    /// Online catalog-backed point indexes by `(label_or_type, property)`.
51    pub node_point_indexes: BTreeSet<(String, String)>,
52    pub relationship_point_indexes: BTreeSet<(String, String)>,
53    /// Online catalog-backed vector indexes by `(label_or_type, property)`.
54    /// Tracked alongside the other index scopes so the optimizer / planner
55    /// can see them in stats fingerprints, though kNN currently goes
56    /// through a flat per-query scan rather than a dedicated structure.
57    pub node_vector_indexes: BTreeSet<(String, String)>,
58    pub relationship_vector_indexes: BTreeSet<(String, String)>,
59}
60
61impl GraphStats {
62    /// Selectivity of an equality predicate `label:prop = value`.
63    /// Returns `Some(rows)` when we have enough info to answer; `None`
64    /// when the optimizer should fall back to its conservative default.
65    pub fn estimate_node_property_equality(&self, label: &str, property: &str) -> Option<u64> {
66        let total = self.nodes_by_label.get(label).copied()? as u64;
67        let distinct = self
68            .node_distinct_values
69            .get(&(label.to_string(), property.to_string()))
70            .copied()
71            .unwrap_or(1)
72            .max(1) as u64;
73        // Uniform-distribution heuristic: each value owns
74        // ⌈total / distinct⌉ rows.
75        Some(total.div_ceil(distinct))
76    }
77
78    pub fn label_count(&self, label: &str) -> Option<u64> {
79        self.nodes_by_label.get(label).copied().map(|c| c as u64)
80    }
81
82    pub fn relationship_type_count(&self, rel_type: &str) -> Option<u64> {
83        self.relationships_by_type
84            .get(rel_type)
85            .copied()
86            .map(|c| c as u64)
87    }
88
89    pub fn fingerprint(&self) -> u64 {
90        let mut hasher = DefaultHasher::new();
91        self.node_count.hash(&mut hasher);
92        self.relationship_count.hash(&mut hasher);
93        self.nodes_by_label.hash(&mut hasher);
94        self.relationships_by_type.hash(&mut hasher);
95        self.node_distinct_values.hash(&mut hasher);
96        self.relationship_distinct_values.hash(&mut hasher);
97        self.node_range_indexes.hash(&mut hasher);
98        self.relationship_range_indexes.hash(&mut hasher);
99        self.node_text_indexes.hash(&mut hasher);
100        self.relationship_text_indexes.hash(&mut hasher);
101        self.node_point_indexes.hash(&mut hasher);
102        self.relationship_point_indexes.hash(&mut hasher);
103        self.node_vector_indexes.hash(&mut hasher);
104        self.relationship_vector_indexes.hash(&mut hasher);
105        hasher.finish()
106    }
107
108    pub fn has_node_range_index(&self, label: &str, property: &str) -> bool {
109        self.node_range_indexes
110            .contains(&(label.to_owned(), property.to_owned()))
111    }
112
113    pub fn has_node_text_index(&self, label: &str, property: &str) -> bool {
114        self.node_text_indexes
115            .contains(&(label.to_owned(), property.to_owned()))
116    }
117
118    pub fn has_node_point_index(&self, label: &str, property: &str) -> bool {
119        self.node_point_indexes
120            .contains(&(label.to_owned(), property.to_owned()))
121    }
122
123    pub fn has_relationship_range_index(&self, rel_type: &str, property: &str) -> bool {
124        self.relationship_range_indexes
125            .contains(&(rel_type.to_owned(), property.to_owned()))
126    }
127
128    pub fn has_relationship_text_index(&self, rel_type: &str, property: &str) -> bool {
129        self.relationship_text_indexes
130            .contains(&(rel_type.to_owned(), property.to_owned()))
131    }
132
133    pub fn has_relationship_point_index(&self, rel_type: &str, property: &str) -> bool {
134        self.relationship_point_indexes
135            .contains(&(rel_type.to_owned(), property.to_owned()))
136    }
137
138    pub fn has_node_vector_index(&self, label: &str, property: &str) -> bool {
139        self.node_vector_indexes
140            .contains(&(label.to_owned(), property.to_owned()))
141    }
142
143    pub fn has_relationship_vector_index(&self, rel_type: &str, property: &str) -> bool {
144        self.relationship_vector_indexes
145            .contains(&(rel_type.to_owned(), property.to_owned()))
146    }
147}
lora_store/memory/stats.rs

lora_store/memory/
stats.rs
