diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 7e7b2ebf07..d2e6a9f6a9 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -264,12 +264,7 @@ impl DatalogExecutor { let planned_patterns = optimizer::plan(patterns, &self.indexes); // Match all patterns in planned order and get bindings - let bindings = matcher.match_patterns( - &planned_patterns - .into_iter() - .map(|(p, _hint)| p) - .collect::>(), - ); + let bindings = matcher.match_patterns_with_hints(&planned_patterns); // Acquire the function registry once; used by apply_or_clauses, not_body_matches, // apply_expr_clauses, and apply_post_processing below. diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index d6e61725c3..9971f5b61e 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -1,3 +1,4 @@ +use super::optimizer::IndexHint; use super::types::{AttributeSpec, EdnValue, Pattern, PseudoAttr}; use crate::graph::FactStorage; use crate::graph::types::{EntityId, Fact, Value}; @@ -252,6 +253,110 @@ impl PatternMatcher { results } + /// Match multiple patterns with index hints for optimized lookups. + pub fn match_patterns_with_hints(&self, patterns: &[(Pattern, IndexHint)]) -> Vec { + if patterns.is_empty() { + return vec![HashMap::new()]; + } + + // Start with the first pattern + let mut results = self.match_pattern_with_hint(&patterns[0].0, &patterns[0].1); + + // Join with each subsequent pattern + for (pattern, _hint) in &patterns[1..] { + results = self.join_with_pattern(results, pattern); + } + + results + } + + /// Match a single pattern with an index hint for optimized lookup. + fn match_pattern_with_hint(&self, pattern: &Pattern, hint: &IndexHint) -> Vec { + // Get matching fact references from index + let fact_refs = self.lookup_with_hint(pattern, hint); + + // If no index lookup possible, fall back to full scan + if fact_refs.is_empty() { + return self.match_pattern(pattern); + } + + // Get all facts and filter by the fact refs from index lookup + let facts = self.get_facts(); + + let mut results = Vec::new(); + for fact in facts { + if let Some(bindings) = self.match_fact_against_pattern(&fact, pattern) { + results.push(bindings); + } + } + + results + } + + /// Look up fact references using the index based on pattern and hint. + fn lookup_with_hint( + &self, + pattern: &Pattern, + hint: &IndexHint, + ) -> Vec { + let indexes = &self.indexes; + + match hint { + IndexHint::Eavt => { + // If entity is bound, use EAVT entity lookup + if let EdnValue::Uuid(entity) = &pattern.entity { + return indexes.lookup_eavt_entity(*entity); + } + // Fall back to full scan + vec![] + } + IndexHint::Aevt => { + // If attribute is bound, use AEVT attribute lookup + if let AttributeSpec::Real(EdnValue::Keyword(attr)) = &pattern.attribute { + return indexes.lookup_aevt_attr(attr); + } + // Fall back to full scan + vec![] + } + IndexHint::Avet => { + // If attribute and value are bound, use AVET + let attr_bound = match &pattern.attribute { + AttributeSpec::Real(edn) => { + if let EdnValue::Keyword(attr) = edn { + Some(attr.clone()) + } else { + None + } + } + _ => None, + }; + let value_bound = match &pattern.value { + EdnValue::Keyword(k) => Some(Value::Keyword(k.clone())), + EdnValue::String(s) => Some(Value::String(s.clone())), + EdnValue::Integer(i) => Some(Value::Integer(*i)), + EdnValue::Float(f) => Some(Value::Float(*f)), + EdnValue::Boolean(b) => Some(Value::Boolean(*b)), + EdnValue::Uuid(u) => Some(Value::Ref(*u)), + _ => None, + }; + + if let (Some(attr), Some(value)) = (attr_bound, value_bound) { + return indexes.lookup_avet_attr_value(&attr, &value); + } + // Fall back to full scan + vec![] + } + IndexHint::Vaet => { + // If value is a Ref, use VAET reverse lookup + if let EdnValue::Uuid(target) = &pattern.value { + return indexes.lookup_vaet_ref(*target); + } + // Fall back to full scan + vec![] + } + } + } + /// Match multiple patterns starting from existing seed bindings. /// /// For each seed binding, extends it by matching all patterns in sequence. diff --git a/src/storage/index.rs b/src/storage/index.rs index b1747714fb..21f6dca659 100644 --- a/src/storage/index.rs +++ b/src/storage/index.rs @@ -202,6 +202,111 @@ impl Indexes { ); } } + + /// Query EAVT index for a specific entity (returns all facts for that entity). + pub fn lookup_eavt_entity(&self, entity: EntityId) -> Vec { + let start = EavtKey { + entity, + attribute: String::new(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + }; + // Use exclusive range with a very high attribute string + let end = EavtKey { + entity, + attribute: String::from("zzzzzzzzzzzzzzzzzz"), + valid_from: i64::MAX, + valid_to: i64::MAX, + tx_count: u64::MAX, + }; + self.eavt.range(start..end).map(|(_, v)| *v).collect() + } + + /// Query EAVT index for entity + attribute. + pub fn lookup_eavt_entity_attr(&self, entity: EntityId, attribute: &str) -> Vec { + let start = EavtKey { + entity, + attribute: attribute.to_string(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + }; + let end = EavtKey { + entity, + attribute: attribute.to_string(), + valid_from: i64::MAX, + valid_to: i64::MAX, + tx_count: u64::MAX, + }; + self.eavt.range(start..=end).map(|(_, v)| *v).collect() + } + + /// Query AEVT index for a specific attribute (returns all facts with that attribute). + pub fn lookup_aevt_attr(&self, attribute: &str) -> Vec { + let max_uuid = uuid::Uuid::parse_str("ffffffff-ffff-ffff-ffff-ffffffffffff").unwrap(); + let start = AevtKey { + attribute: attribute.to_string(), + entity: EntityId::default(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + }; + let end = AevtKey { + attribute: attribute.to_string(), + entity: max_uuid, + valid_from: i64::MAX, + valid_to: i64::MAX, + tx_count: u64::MAX, + }; + self.aevt.range(start..=end).map(|(_, v)| *v).collect() + } + + /// Query AVET index for attribute + value. + pub fn lookup_avet_attr_value(&self, attribute: &str, value: &Value) -> Vec { + let max_uuid = uuid::Uuid::parse_str("ffffffff-ffff-ffff-ffff-ffffffffffff").unwrap(); + let value_bytes = encode_value(value); + let start = AvetKey { + attribute: attribute.to_string(), + value_bytes: value_bytes.clone(), + valid_from: i64::MIN, + valid_to: i64::MIN, + entity: EntityId::default(), + tx_count: 0, + }; + let end = AvetKey { + attribute: attribute.to_string(), + value_bytes, + valid_from: i64::MAX, + valid_to: i64::MAX, + entity: max_uuid, + tx_count: u64::MAX, + }; + self.avet.range(start..=end).map(|(_, v)| *v).collect() + } + + /// Query VAET index for ref target (reverse references). + pub fn lookup_vaet_ref(&self, target: EntityId) -> Vec { + let max_uuid = uuid::Uuid::parse_str("ffffffff-ffff-ffff-ffff-ffffffffffff").unwrap(); + let start = VaetKey { + ref_target: target, + attribute: String::new(), + valid_from: i64::MIN, + valid_to: i64::MIN, + source_entity: EntityId::default(), + tx_count: 0, + }; + let end = VaetKey { + ref_target: target, + // Use max char to include all attributes + attribute: char::MAX.to_string(), + valid_from: i64::MAX, + valid_to: i64::MAX, + source_entity: max_uuid, + tx_count: u64::MAX, + }; + self.vaet.range(start..=end).map(|(_, v)| *v).collect() + } } #[cfg(test)]