Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
7 changes: 1 addition & 6 deletions src/query/datalog/executor.rs
Original file line number Diff line number Diff line change
Expand Up @@ -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::<Vec<_>>(),
);
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.
Expand Down
105 changes: 105 additions & 0 deletions src/query/datalog/matcher.rs
Original file line number Diff line number Diff line change
@@ -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};
Expand Down Expand Up @@ -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<Bindings> {
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<Bindings> {
// 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<crate::storage::index::FactRef> {
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.
Expand Down
105 changes: 105 additions & 0 deletions src/storage/index.rs
Original file line number Diff line number Diff line change
Expand Up @@ -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<FactRef> {
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<FactRef> {
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<FactRef> {
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<FactRef> {
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<FactRef> {
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)]
Expand Down
Loading