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
148
149
150
151
152
153
154
155
156
157
//! Query-local equality hash index for cross-MATCH joins on non-id properties.
//!
//! Built once per `execute_match` call when the heuristic detects a single
//! typed-node pattern carrying exactly one `EqualsVar` / `EqualsNodeProp`
//! matcher. Probed per outer row, replacing N×M property scans with O(N+M)
//! work. Mirrors the per-query R-tree pattern in [`super::spatial_join`].
//!
//! The index is dropped when the executor goes out of scope; it never
//! mutates [`DirGraph::property_indices`].
use super::helpers::resolve_node_property;
use super::ResultRow;
use crate::datatypes::values::Value;
use crate::graph::core::pattern_matching::{NodePattern, Pattern, PatternElement, PropertyMatcher};
use crate::graph::schema::DirGraph;
use crate::graph::storage::GraphRead;
use petgraph::graph::NodeIndex;
use std::collections::HashMap;
/// Activation threshold: only build the index when there are at least this
/// many outer rows. Below it, the per-row pattern execution is already
/// cheap enough that the build cost doesn't pay back.
pub(super) const TRANSIENT_INDEX_THRESHOLD: usize = 64;
/// Per-query equality index over a single typed property.
pub(super) struct TransientEqIndex {
/// Pattern variable bound by an index probe (e.g. `"pg"`).
pub(super) bind_var: String,
/// How to resolve the per-row probe value.
pub(super) resolution: ProbeResolution,
/// Built index: property value → matching `NodeIndex`(es).
pub(super) by_value: HashMap<Value, Vec<NodeIndex>>,
}
/// How to read the probe value from a row.
pub(super) enum ProbeResolution {
/// Resolved from `row.projected[var]` — pushed by the planner from
/// `WITH x AS pnum MATCH (n {prop: pnum})` style joins.
Projected(String),
/// Resolved by reading `row.node_bindings[var]`'s property `prop`.
/// Pushed from correlated `MATCH (a) MATCH (b) WHERE b.x = a.y`.
NodeProp { var: String, prop: String },
}
impl TransientEqIndex {
/// Try to build a transient index for `pattern`. Returns `None` when:
/// - the pattern shape doesn't qualify (not a single typed node, more
/// than one matcher, etc.),
/// - the existing-row count is below the threshold,
/// - a persistent index already covers `(node_type, property)`,
/// - or the type has no live nodes.
pub(super) fn try_build(
graph: &DirGraph,
pattern: &Pattern,
existing_row_count: usize,
) -> Option<TransientEqIndex> {
if existing_row_count < TRANSIENT_INDEX_THRESHOLD {
return None;
}
let np = extract_single_node_pattern(pattern)?;
// Multi-label patterns (`MATCH (n:A:B)`) need a label intersection
// the single-property eq-index can't express — fall to the matcher.
if !np.extra_labels.is_empty() {
return None;
}
let node_type = np.node_type.as_deref()?.to_string();
let bind_var = np.variable.as_deref()?.to_string();
let props = np.properties.as_ref()?;
if props.len() != 1 {
return None;
}
let (property, matcher) = props.iter().next()?;
// The `id` / `title` virtuals are node *identity*, not stored
// properties: `resolve_node_property` maps them to `node.id()` /
// `node.title()`, and when the id-field column was consumed as
// identity at load the stored value is `Null`. Either way, building an
// equality hash-index over them is wrong — it yields an empty/partial
// map, so every probe misses and the MATCH returns nothing (the bug
// that surfaced as `UNWIND $ids MATCH (n {id:i})` dropping all rows
// once the list crossed the 64-row activation threshold). Identity
// lookups already have their own fast seek path, so bail and let the
// per-row matcher handle them.
let resolved_prop = graph.resolve_alias(np.node_type.as_deref()?, property);
if resolved_prop == "id" || resolved_prop == "title" {
return None;
}
let resolution = match matcher {
PropertyMatcher::EqualsVar(name) => ProbeResolution::Projected(name.clone()),
PropertyMatcher::EqualsNodeProp { var, prop } => ProbeResolution::NodeProp {
var: var.clone(),
prop: prop.clone(),
},
_ => return None,
};
// Don't double-build when a persistent index already exists.
if graph.has_any_index(&node_type, property) {
return None;
}
// Union primary + secondary candidates (identical to a
// `type_indices` clone on single-label graphs).
let nodes = graph.nodes_with_label(&node_type);
if nodes.is_empty() {
return None;
}
let mut by_value: HashMap<Value, Vec<NodeIndex>> = HashMap::with_capacity(nodes.len());
for idx in nodes {
if let Some(node) = graph.graph.node_view(idx) {
let val = resolve_node_property(node, property, graph);
if !matches!(val, Value::Null) {
by_value.entry(val).or_default().push(idx);
}
}
}
Some(TransientEqIndex {
bind_var,
resolution,
by_value,
})
}
/// Resolve the probe value for this row. `None` means "no candidates":
/// either the variable is missing or the value is null (Cypher
/// equality with null never matches).
pub(super) fn probe_value(&self, row: &ResultRow, graph: &DirGraph) -> Option<Value> {
let value = match &self.resolution {
ProbeResolution::Projected(var) => row.projected.get(var.as_str()).cloned()?,
ProbeResolution::NodeProp { var, prop } => {
let idx = row.node_bindings.get(var.as_str())?;
let node = graph.graph.node_view(*idx)?;
resolve_node_property(node, prop, graph)
}
};
if matches!(value, Value::Null) {
None
} else {
Some(value)
}
}
/// Look up matching node indices by value. Empty slice if no match.
pub(super) fn lookup(&self, value: &Value) -> &[NodeIndex] {
self.by_value
.get(value)
.map(|v| v.as_slice())
.unwrap_or(&[])
}
}
fn extract_single_node_pattern(pattern: &Pattern) -> Option<&NodePattern> {
if pattern.elements.len() != 1 {
return None;
}
match &pattern.elements[0] {
PatternElement::Node(np) => Some(np),
_ => None,
}
}