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