From a732fa328197965b45a2a4038e2b89007593db7a Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 3 Apr 2026 10:31:04 +0530 Subject: [PATCH] perf(query): implement index-guided lookups Issue: PatternMatcher ignores indexes, always does full scan Changes: - Add lookup methods to Indexes: lookup_eavt_entity, lookup_eavt_entity_attr, lookup_aevt_attr, lookup_avet_attr_value, lookup_vaet_ref - Add match_patterns_with_hints to PatternMatcher that uses index hints - Add lookup_with_hint to use appropriate index based on IndexHint - Update executor to pass (Pattern, IndexHint) pairs instead of just patterns The matcher now uses index lookups when hints are available, falling back to full scan when index lookup is not applicable (e.g., variable bindings). --- src/query/datalog/executor.rs | 7 +-- src/query/datalog/matcher.rs | 105 ++++++++++++++++++++++++++++++++++ src/storage/index.rs | 105 ++++++++++++++++++++++++++++++++++ 3 files changed, 211 insertions(+), 6 deletions(-) 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)]