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
16use super::index_catalog::{StoredIndexEntity, StoredIndexKind};
17
18/// `(label or relationship type, property key) → estimated distinct
19/// values`.
20pub type DistinctValues = BTreeMap<(String, String), usize>;
21
22/// Snapshot of graph cardinality. Populated by the storage backend
23/// (see [`super::InMemoryGraph::stats`]).
24#[derive(Debug, Default, Clone, PartialEq, Eq)]
25pub struct GraphStats {
26    /// Total live node count.
27    pub node_count: usize,
28    /// Total live relationship count.
29    pub relationship_count: usize,
30    /// Per-label node count. `nodes_by_label[label].len()`.
31    pub nodes_by_label: BTreeMap<String, usize>,
32    /// Per-rel-type relationship count. `relationships_by_type[type].len()`.
33    pub relationships_by_type: BTreeMap<String, usize>,
34    /// Per-(label, property) approximate distinct value count, for
35    /// every property key that a live node with that label carries,
36    /// indexed or not. Estimated from a distinct-value sketch kept on
37    /// every write (see `memory::distinct_stats`): a function of the live
38    /// data alone, so a restarted process, the writer and a process with
39    /// a different lookup history get the same numbers. Absent only for
40    /// keys no node of the label has (or whose values the hash index
41    /// can't key: NaN, durations, points, vectors). Shared: the store
42    /// reuses one map while the estimates don't change.
43    pub node_distinct_values: Arc<DistinctValues>,
44    /// Per-(relationship type, property) distinct value count; as above.
45    pub relationship_distinct_values: Arc<DistinctValues>,
46    /// Online catalog-backed range indexes by `(label_or_type, property)`.
47    pub node_range_indexes: BTreeSet<(String, String)>,
48    pub relationship_range_indexes: BTreeSet<(String, String)>,
49    /// Online catalog-backed text indexes by `(label_or_type, property)`.
50    pub node_text_indexes: BTreeSet<(String, String)>,
51    pub relationship_text_indexes: BTreeSet<(String, String)>,
52    /// Online catalog-backed point indexes by `(label_or_type, property)`.
53    pub node_point_indexes: BTreeSet<(String, String)>,
54    pub relationship_point_indexes: BTreeSet<(String, String)>,
55    /// Online catalog-backed vector indexes by `(label_or_type, property)`.
56    /// Tracked alongside the other index scopes so the optimizer / planner
57    /// can see them in stats fingerprints, though kNN currently goes
58    /// through a flat per-query scan rather than a dedicated structure.
59    pub node_vector_indexes: BTreeSet<(String, String)>,
60    pub relationship_vector_indexes: BTreeSet<(String, String)>,
61    /// List elements held by the RANGE index scopes whose property holds
62    /// lists, by `(label_or_type, property)`: what an element seek
63    /// (`$x IN n.list`) is costed from. Exact counts, kept on every write.
64    pub node_list_elements: BTreeMap<(String, String), ListElementStats>,
65    pub relationship_list_elements: BTreeMap<(String, String), ListElementStats>,
66}
67
68/// List elements in one RANGE index scope (see
69/// [`GraphStats::node_list_elements`]).
70#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, Hash)]
71pub struct ListElementStats {
72    /// Distinct elements across every list.
73    pub distinct: usize,
74    /// `(element, entity)` pairs: each list counts each distinct element
75    /// it holds once.
76    pub postings: usize,
77}
78
79impl ListElementStats {
80    /// Entities one element seek finds, on average.
81    pub fn per_element(&self) -> u64 {
82        (self.postings as u64).div_ceil(self.distinct.max(1) as u64)
83    }
84}
85
86/// Builds a [`GraphStats::plan_signature`]: a hash of every input the
87/// planner reads from the stats, with cardinalities coarsened to
88/// power-of-two buckets. Backends feed it the same items `GraphStats`
89/// holds, in a deterministic order, without building the maps.
90pub struct PlanSignature {
91    hasher: DefaultHasher,
92}
93
94impl Default for PlanSignature {
95    fn default() -> Self {
96        Self::new()
97    }
98}
99
100impl PlanSignature {
101    pub fn new() -> Self {
102        Self {
103            hasher: DefaultHasher::new(),
104        }
105    }
106
107    /// Bucket of a cardinality: 0 for 0, else its bit length (1, 2-3,
108    /// 4-7, ...). Cost estimates within one bucket are within a factor
109    /// of two of each other.
110    pub fn bucket(count: usize) -> u32 {
111        usize::BITS - count.leading_zeros()
112    }
113
114    pub fn totals(&mut self, nodes: usize, relationships: usize) {
115        (0u8, Self::bucket(nodes), Self::bucket(relationships)).hash(&mut self.hasher);
116    }
117
118    /// A label present in the stats (even with no nodes left: an absent
119    /// label and an empty one estimate differently).
120    pub fn label(&mut self, label: &str, nodes: usize) {
121        (1u8, label, Self::bucket(nodes)).hash(&mut self.hasher);
122    }
123
124    pub fn relationship_type(&mut self, rel_type: &str, relationships: usize) {
125        (2u8, rel_type, Self::bucket(relationships)).hash(&mut self.hasher);
126    }
127
128    pub fn node_distinct(&mut self, label: &str, property: &str, distinct: usize) {
129        (3u8, label, property, Self::bucket(distinct)).hash(&mut self.hasher);
130    }
131
132    pub fn relationship_distinct(&mut self, rel_type: &str, property: &str, distinct: usize) {
133        (4u8, rel_type, property, Self::bucket(distinct)).hash(&mut self.hasher);
134    }
135
136    /// An online range / text / point / vector index scope, as the
137    /// `*_indexes` sets of [`GraphStats`] hold them.
138    pub fn index(
139        &mut self,
140        entity: StoredIndexEntity,
141        kind: StoredIndexKind,
142        label: &str,
143        property: &str,
144    ) {
145        (5u8, entity, kind.as_str(), label, property).hash(&mut self.hasher);
146    }
147
148    /// A RANGE index scope holding list elements, by the entities one
149    /// element seek finds on average.
150    pub fn list_elements(
151        &mut self,
152        entity: StoredIndexEntity,
153        label: &str,
154        property: &str,
155        stats: ListElementStats,
156    ) {
157        (
158            6u8,
159            entity,
160            label,
161            property,
162            Self::bucket(stats.per_element() as usize),
163        )
164            .hash(&mut self.hasher);
165    }
166
167    pub fn finish(&self) -> u64 {
168        self.hasher.finish()
169    }
170}
171
172impl GraphStats {
173    /// Selectivity of an equality predicate `label:prop = value`.
174    /// Returns `Some(rows)` when we have enough info to answer; `None`
175    /// when the optimizer should fall back to its conservative default.
176    pub fn estimate_node_property_equality(&self, label: &str, property: &str) -> Option<u64> {
177        let total = self.nodes_by_label.get(label).copied()? as u64;
178        // No distinct count: no node of the label holds the key (G-75), so
179        // an equality on it finds nothing. Read as the whole label, it lost
180        // to any other indexed equality beside it.
181        let Some(&distinct) = self
182            .node_distinct_values
183            .get(&(label.to_string(), property.to_string()))
184        else {
185            return Some(0);
186        };
187        // Uniform-distribution heuristic: each value owns
188        // ⌈total / distinct⌉ rows.
189        Some(total.div_ceil(distinct.max(1) as u64))
190    }
191
192    /// Rows an element seek `$x IN label.property` finds, from the RANGE
193    /// index on the pair: the average entities per element, or 0 when
194    /// the indexed values hold no list element. `None` without the index.
195    pub fn estimate_node_list_element(&self, label: &str, property: &str) -> Option<u64> {
196        let scope = (label.to_owned(), property.to_owned());
197        if !self.node_range_indexes.contains(&scope) {
198            return None;
199        }
200        Some(
201            self.node_list_elements
202                .get(&scope)
203                .map_or(0, ListElementStats::per_element),
204        )
205    }
206
207    /// Mirror of [`Self::estimate_node_list_element`] for relationships.
208    pub fn estimate_relationship_list_element(
209        &self,
210        rel_type: &str,
211        property: &str,
212    ) -> Option<u64> {
213        let scope = (rel_type.to_owned(), property.to_owned());
214        if !self.relationship_range_indexes.contains(&scope) {
215            return None;
216        }
217        Some(
218            self.relationship_list_elements
219                .get(&scope)
220                .map_or(0, ListElementStats::per_element),
221        )
222    }
223
224    pub fn label_count(&self, label: &str) -> Option<u64> {
225        self.nodes_by_label.get(label).copied().map(|c| c as u64)
226    }
227
228    pub fn relationship_type_count(&self, rel_type: &str) -> Option<u64> {
229        self.relationships_by_type
230            .get(rel_type)
231            .copied()
232            .map(|c| c as u64)
233    }
234
235    pub fn fingerprint(&self) -> u64 {
236        let mut hasher = DefaultHasher::new();
237        self.node_count.hash(&mut hasher);
238        self.relationship_count.hash(&mut hasher);
239        self.nodes_by_label.hash(&mut hasher);
240        self.relationships_by_type.hash(&mut hasher);
241        self.node_distinct_values.hash(&mut hasher);
242        self.relationship_distinct_values.hash(&mut hasher);
243        self.node_range_indexes.hash(&mut hasher);
244        self.relationship_range_indexes.hash(&mut hasher);
245        self.node_text_indexes.hash(&mut hasher);
246        self.relationship_text_indexes.hash(&mut hasher);
247        self.node_point_indexes.hash(&mut hasher);
248        self.relationship_point_indexes.hash(&mut hasher);
249        self.node_vector_indexes.hash(&mut hasher);
250        self.relationship_vector_indexes.hash(&mut hasher);
251        self.node_list_elements.hash(&mut hasher);
252        self.relationship_list_elements.hash(&mut hasher);
253        hasher.finish()
254    }
255
256    /// Hash of what the planner reads from these stats, with every
257    /// cardinality coarsened to a power-of-two bucket (see
258    /// [`PlanSignature`]). Two stats with the same signature have the
259    /// same labels, types, counted keys and online index scopes, and
260    /// counts within a factor of two: a plan made for one is a sound
261    /// and reasonable plan for the other. Plans never depend on stats
262    /// for correctness, only for cost.
263    pub fn plan_signature(&self) -> u64 {
264        let mut sig = PlanSignature::new();
265        sig.totals(self.node_count, self.relationship_count);
266        for (label, count) in &self.nodes_by_label {
267            sig.label(label, *count);
268        }
269        for (rel_type, count) in &self.relationships_by_type {
270            sig.relationship_type(rel_type, *count);
271        }
272        for ((label, property), distinct) in self.node_distinct_values.iter() {
273            sig.node_distinct(label, property, *distinct);
274        }
275        for ((rel_type, property), distinct) in self.relationship_distinct_values.iter() {
276            sig.relationship_distinct(rel_type, property, *distinct);
277        }
278        let scopes = [
279            (
280                StoredIndexEntity::Node,
281                StoredIndexKind::Range,
282                &self.node_range_indexes,
283            ),
284            (
285                StoredIndexEntity::Node,
286                StoredIndexKind::Text,
287                &self.node_text_indexes,
288            ),
289            (
290                StoredIndexEntity::Node,
291                StoredIndexKind::Point,
292                &self.node_point_indexes,
293            ),
294            (
295                StoredIndexEntity::Node,
296                StoredIndexKind::Vector,
297                &self.node_vector_indexes,
298            ),
299            (
300                StoredIndexEntity::Relationship,
301                StoredIndexKind::Range,
302                &self.relationship_range_indexes,
303            ),
304            (
305                StoredIndexEntity::Relationship,
306                StoredIndexKind::Text,
307                &self.relationship_text_indexes,
308            ),
309            (
310                StoredIndexEntity::Relationship,
311                StoredIndexKind::Point,
312                &self.relationship_point_indexes,
313            ),
314            (
315                StoredIndexEntity::Relationship,
316                StoredIndexKind::Vector,
317                &self.relationship_vector_indexes,
318            ),
319        ];
320        for (entity, kind, set) in scopes {
321            for (label, property) in set {
322                sig.index(entity, kind, label, property);
323            }
324        }
325        for (entity, elements) in [
326            (StoredIndexEntity::Node, &self.node_list_elements),
327            (
328                StoredIndexEntity::Relationship,
329                &self.relationship_list_elements,
330            ),
331        ] {
332            for ((label, property), stats) in elements {
333                sig.list_elements(entity, label, property, *stats);
334            }
335        }
336        sig.finish()
337    }
338
339    pub fn has_node_range_index(&self, label: &str, property: &str) -> bool {
340        self.node_range_indexes
341            .contains(&(label.to_owned(), property.to_owned()))
342    }
343
344    pub fn has_node_text_index(&self, label: &str, property: &str) -> bool {
345        self.node_text_indexes
346            .contains(&(label.to_owned(), property.to_owned()))
347    }
348
349    pub fn has_node_point_index(&self, label: &str, property: &str) -> bool {
350        self.node_point_indexes
351            .contains(&(label.to_owned(), property.to_owned()))
352    }
353
354    pub fn has_relationship_range_index(&self, rel_type: &str, property: &str) -> bool {
355        self.relationship_range_indexes
356            .contains(&(rel_type.to_owned(), property.to_owned()))
357    }
358
359    pub fn has_relationship_text_index(&self, rel_type: &str, property: &str) -> bool {
360        self.relationship_text_indexes
361            .contains(&(rel_type.to_owned(), property.to_owned()))
362    }
363
364    pub fn has_relationship_point_index(&self, rel_type: &str, property: &str) -> bool {
365        self.relationship_point_indexes
366            .contains(&(rel_type.to_owned(), property.to_owned()))
367    }
368
369    pub fn has_node_vector_index(&self, label: &str, property: &str) -> bool {
370        self.node_vector_indexes
371            .contains(&(label.to_owned(), property.to_owned()))
372    }
373
374    pub fn has_relationship_vector_index(&self, rel_type: &str, property: &str) -> bool {
375        self.relationship_vector_indexes
376            .contains(&(rel_type.to_owned(), property.to_owned()))
377    }
378}
lora_store/memory/stats.rs

lora_store/memory/
stats.rs
