From b390400a61d2d01e0b31ee7e8dbb74dda46e0d2f Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 15 May 2026 13:29:50 +0530 Subject: [PATCH 1/9] =?UTF-8?q?perf:=20pre-compute=20not/not-join=20exclus?= =?UTF-8?q?ion=20sets=20=E2=80=94=20O(N=C2=B2)=20=E2=86=92=20O(N)=20(#202)?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Replace the per-binding not-filter loop in execute_query with a pre-computed exclusion set approach: run each not/not-join body once against filtered_facts, build a HashSet of excluded join-key tuples, then probe O(1) per outer binding. Includes normalize_value() to reconcile Value::Keyword vs Value::Ref entity representations across body and outer bindings. Expr-only bodies fall through to the existing not_body_matches slow path unchanged. Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/executor.rs | 375 ++++++++++++++++++++++++++++++++-- 1 file changed, 356 insertions(+), 19 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 0fab15987d..6653a2f8ea 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -546,30 +546,236 @@ impl DatalogExecutor { let not_filtered: Vec<_> = if not_clauses.is_empty() && not_join_clauses.is_empty() { bindings } else { + // Pre-compute exclusion sets — one evaluation per not-body, not per outer binding. + // + // For each not-body, run pattern matching once against `filtered_facts` to get + // all bindings where the body is satisfiable. Then collect the "join keys" (the + // subset of variables that appear in the outer bindings) into a HashSet. + // The filter loop below does one O(1) probe per outer binding instead of a full + // pattern match. + // + // Edge case: expr-only bodies (no patterns) produce no pre-computed set and fall + // through to `not_body_matches` as before (rare, already fast). + use std::collections::HashSet; + + // --- Not bodies --- + // Each element: either Some(HashSet of excluded join-key tuples) or None (expr-only, + // use slow path). + let not_exclusion_sets: Vec>>> = not_clauses + .iter() + .map(|not_body| { + let patterns: Vec<_> = not_body + .iter() + .filter_map(|c| match c { + WhereClause::Pattern(p) => Some(p.clone()), + _ => None, + }) + .collect(); + if patterns.is_empty() { + // Expr-only body: no pre-computation possible. + return None; + } + let matcher = + PatternMatcher::from_slice_with_valid_at( + filtered_facts.clone(), + valid_at_value.clone(), + ); + let body_bindings = matcher.match_patterns(&patterns); + // Store all body bindings as sorted (key, value) vecs for probing. + let exclusion_set: HashSet> = body_bindings + .into_iter() + .map(|mut b| { + // Drop hidden metadata keys (prefixed `__f`) + b.retain(|k, _| !k.starts_with("__f")); + let mut kv: Vec<(String, Value)> = b.into_iter().collect(); + kv.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + kv + }) + .collect(); + Some(exclusion_set) + }) + .collect(); + + // --- Not-join bodies --- + // Each entry: Some((key_vars, HashSet)) where key_vars are the join_vars that + // actually appear in the body bindings (the intersection of join_vars and body-bound + // vars). This handles cases like `not-join [?u ?r]` where the body only binds `?r`. + // + // Values are normalized: Value::Keyword(k) that represents an entity keyword is + // converted to Value::Ref(uuid) so that probe keys from the outer binding (which + // may store entity references as keywords) match the body bindings (which bind + // entity fields as Value::Ref). + let not_join_exclusion_sets: Vec, HashSet>)>> = + not_join_clauses + .iter() + .map(|(join_vars, nj_clauses)| { + let patterns: Vec<_> = nj_clauses + .iter() + .filter_map(|c| match c { + WhereClause::Pattern(p) => Some(p.clone()), + _ => None, + }) + .collect(); + if patterns.is_empty() { + return None; + } + let matcher = + PatternMatcher::from_slice_with_valid_at( + filtered_facts.clone(), + valid_at_value.clone(), + ); + let body_bindings = matcher.match_patterns(&patterns); + if body_bindings.is_empty() { + // No body bindings → no exclusions. Use empty exclusion set with + // all join_vars as key so probe returns not-found for all. + return Some((join_vars.clone(), HashSet::new())); + } + // Determine which join_vars actually appear in body bindings. + // Only those can be used as the exclusion key. + let key_vars: Vec = { + let sample = &body_bindings[0]; + join_vars + .iter() + .filter(|v| sample.contains_key(*v)) + .cloned() + .collect() + }; + // Project to key_vars only (subset of join_vars), normalizing values. + let exclusion_set: HashSet> = body_bindings + .into_iter() + .map(|b| { + let mut kv: Vec<(String, Value)> = key_vars + .iter() + .filter_map(|v| { + b.get(v).map(|val| (v.clone(), normalize_value(val))) + }) + .collect(); + kv.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + kv + }) + .collect(); + Some((key_vars, exclusion_set)) + }) + .collect(); + bindings .into_iter() .filter(|binding| { - for not_body in ¬_clauses { - if not_body_matches( - not_body, - binding, - filtered_facts.clone(), - valid_at_value.clone(), - ®istry, - ) { - return false; + // Check not-bodies via pre-computed exclusion sets (fast path) or + // via not_body_matches (slow path for expr-only bodies). + for (i, not_body) in not_clauses.iter().enumerate() { + match ¬_exclusion_sets[i] { + Some(exclusion_set) => { + let has_expr = not_body + .iter() + .any(|c| matches!(c, WhereClause::Expr { .. })); + if exclusion_set.is_empty() && !has_expr { + // No excluding bindings → this outer binding is safe. + continue; + } + if !has_expr { + // Fast path: probe exclusion set using the outer binding's + // values for the join variables. + if let Some(sample) = exclusion_set.iter().next() { + let key: Vec<(String, Value)> = sample + .iter() + .filter_map(|(var, _)| { + binding + .get(var) + .map(|val| (var.clone(), val.clone())) + }) + .collect(); + // Only probe if all join vars are bound in the outer binding. + if key.len() == sample.len() + && exclusion_set.contains(&key) + { + return false; + } + continue; + } + } + // Slow path fallback (expr clauses or empty exclusion set with exprs) + if not_body_matches( + not_body, + binding, + filtered_facts.clone(), + valid_at_value.clone(), + ®istry, + ) { + return false; + } + } + None => { + // Expr-only body: slow path. + if not_body_matches( + not_body, + binding, + filtered_facts.clone(), + valid_at_value.clone(), + ®istry, + ) { + return false; + } + } } } - for (join_vars, nj_clauses) in ¬_join_clauses { - // Use the already-acquired registry instead of re-acquiring the lock. - if evaluate_not_join( - join_vars, - nj_clauses, - binding, - filtered_facts.clone(), - ®istry, - ) { - return false; + + // Check not-join-bodies. + for (i, (join_vars, nj_clauses)) in not_join_clauses.iter().enumerate() { + match ¬_join_exclusion_sets[i] { + Some((key_vars, exclusion_set)) => { + let has_expr = nj_clauses + .iter() + .any(|c| matches!(c, WhereClause::Expr { .. })); + if !has_expr { + if key_vars.is_empty() { + // Body bound no join vars: if exclusion set non-empty, + // exclude all outer bindings (body always succeeds). + if !exclusion_set.is_empty() { + return false; + } + continue; + } + // Build probe key from outer binding using key_vars. + // Normalize values so keyword entities match ref entities. + let mut key: Vec<(String, Value)> = key_vars + .iter() + .filter_map(|v| { + binding + .get(v) + .map(|val| (v.clone(), normalize_value(val))) + }) + .collect(); + key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + if key.len() == key_vars.len() + && exclusion_set.contains(&key) + { + return false; + } + continue; + } + // Fall through to slow path if expr clauses present. + if evaluate_not_join( + join_vars, + nj_clauses, + binding, + filtered_facts.clone(), + ®istry, + ) { + return false; + } + } + None => { + if evaluate_not_join( + join_vars, + nj_clauses, + binding, + filtered_facts.clone(), + ®istry, + ) { + return false; + } + } } } true @@ -916,6 +1122,24 @@ impl DatalogExecutor { } } +/// Normalize a `Value` for use as a hash-join key. +/// +/// Entity keywords (`:foo`) and entity refs (`Value::Ref(uuid)`) represent the same +/// entity but appear as different variants depending on whether the value was stored in +/// the entity position (→ `Ref`) or the value position (→ `Keyword`) of a fact. +/// Normalize both to `Value::Ref` so that exclusion-set probes work correctly across +/// these two representations. +fn normalize_value(v: &Value) -> Value { + if let Value::Keyword(k) = v { + use crate::query::datalog::matcher::edn_to_entity_id; + use crate::query::datalog::types::EdnValue; + if let Ok(uuid) = edn_to_entity_id(&EdnValue::Keyword(k.clone())) { + return Value::Ref(uuid); + } + } + v.clone() +} + /// Evaluate a `not` body against the current outer binding. /// /// Returns true if the body "matches" (i.e., the outer binding should be excluded). @@ -4682,3 +4906,116 @@ mod selective_lookup_tests { } } } + +#[cfg(test)] +mod not_hash_join_tests { + use crate::graph::FactStorage; + use crate::query::datalog::executor::DatalogExecutor; + + fn make_not_db(n: usize, excluded: usize) -> DatalogExecutor { + let storage = FactStorage::new(); + let exec = DatalogExecutor::new(storage); + for batch_start in (0..n).step_by(100) { + let batch_end = (batch_start + 100).min(n); + let mut cmd = String::from("(transact ["); + for i in batch_start..batch_end { + cmd.push_str(&format!("[:e{i} :val {i}]", i = i)); + } + cmd.push_str("])"); + exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()) + .unwrap(); + } + for batch_start in (0..excluded).step_by(100) { + let batch_end = (batch_start + 100).min(excluded); + let mut cmd = String::from("(transact ["); + for i in batch_start..batch_end { + cmd.push_str(&format!("[:e{i} :banned true]", i = i)); + } + cmd.push_str("])"); + exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()) + .unwrap(); + } + exec + } + + #[test] + fn not_filter_returns_correct_count() { + let n = 1_000; + let excluded = n / 10; // 100 banned + let exec = make_not_db(n, excluded); + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?e :where [?e :val ?v] (not [?e :banned true])])", + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result + { + assert_eq!( + results.len(), + n - excluded, + "expected {} results after not-filter", + n - excluded + ); + } else { + panic!("expected QueryResults"); + } + } + + #[test] + fn not_join_filter_returns_correct_count() { + let n = 1_000; + let excluded = n / 10; + let storage = FactStorage::new(); + let exec = DatalogExecutor::new(storage); + for batch_start in (0..n).step_by(100) { + let batch_end = (batch_start + 100).min(n); + let mut cmd = String::from("(transact ["); + for i in batch_start..batch_end { + cmd.push_str(&format!("[:e{i} :val {i}]", i = i)); + } + cmd.push_str("])"); + exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()) + .unwrap(); + } + exec.execute( + crate::query::datalog::parser::parse_datalog_command( + "(transact [[:d-bad :status :bad]])", + ) + .unwrap(), + ) + .unwrap(); + for batch_start in (0..excluded).step_by(100) { + let batch_end = (batch_start + 100).min(excluded); + let mut cmd = String::from("(transact ["); + for i in batch_start..batch_end { + cmd.push_str(&format!("[:e{i} :dep :d-bad]", i = i)); + } + cmd.push_str("])"); + exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()) + .unwrap(); + } + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?e :where [?e :val ?v] \ + (not-join [?e] [?e :dep ?d] [?d :status :bad])])", + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result + { + assert_eq!( + results.len(), + n - excluded, + "expected {} results after not-join-filter", + n - excluded + ); + } else { + panic!("expected QueryResults"); + } + } +} From ae9eddccbd1e3d2ad25a1eae202de59eb2d70370 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 15 May 2026 13:37:40 +0530 Subject: [PATCH 2/9] fix: address code review issues in #202 exclusion set implementation - Move has_expr out of per-binding filter closure into pre-compute phase; store alongside exclusion set as (bool, HashSet) tuple for both not and not-join paths, eliminating redundant O(clauses) work per outer binding - Apply normalize_value consistently on the not (non-join) path when building and probing the exclusion set, matching the not-join path; prevents misses when entity values differ between Ref and Keyword variants - Derive key_vars as intersection of join_vars with vars present in ALL body binding rows (fold/all approach), not just the first sample row - Fix not fast path to fall back to not_body_matches when the outer binding is underspecified relative to the exclusion set key, instead of silently allowing the row through with continue - Replace unsafe [i] indexing with zip() iteration to satisfy clippy (reduces clippy errors from 3 to 0) Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/executor.rs | 101 ++++++++++++++++++++-------------- 1 file changed, 61 insertions(+), 40 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 6653a2f8ea..c5429c6b7e 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -559,11 +559,15 @@ impl DatalogExecutor { use std::collections::HashSet; // --- Not bodies --- - // Each element: either Some(HashSet of excluded join-key tuples) or None (expr-only, - // use slow path). - let not_exclusion_sets: Vec>>> = not_clauses + // Each element: either Some((has_expr, HashSet of excluded join-key tuples)) or None + // (expr-only, use slow path). `has_expr` is computed once here during pre-compute, + // not inside the per-binding filter closure. + let not_exclusion_sets: Vec>)>> = not_clauses .iter() .map(|not_body| { + let has_expr = not_body + .iter() + .any(|c| matches!(c, WhereClause::Expr { .. })); let patterns: Vec<_> = not_body .iter() .filter_map(|c| match c { @@ -582,33 +586,42 @@ impl DatalogExecutor { ); let body_bindings = matcher.match_patterns(&patterns); // Store all body bindings as sorted (key, value) vecs for probing. + // Normalize values (e.g. keyword entities → Ref) so that probe keys from + // the outer binding match body bindings regardless of representation. let exclusion_set: HashSet> = body_bindings .into_iter() .map(|mut b| { // Drop hidden metadata keys (prefixed `__f`) b.retain(|k, _| !k.starts_with("__f")); - let mut kv: Vec<(String, Value)> = b.into_iter().collect(); + let mut kv: Vec<(String, Value)> = b + .into_iter() + .map(|(k, v)| (k, normalize_value(&v))) + .collect(); kv.sort_unstable_by(|a, b| a.0.cmp(&b.0)); kv }) .collect(); - Some(exclusion_set) + Some((has_expr, exclusion_set)) }) .collect(); // --- Not-join bodies --- - // Each entry: Some((key_vars, HashSet)) where key_vars are the join_vars that - // actually appear in the body bindings (the intersection of join_vars and body-bound - // vars). This handles cases like `not-join [?u ?r]` where the body only binds `?r`. + // Each entry: Some((has_expr, key_vars, HashSet)) where key_vars are the join_vars + // that actually appear in ALL body binding rows (the intersection of join_vars and + // vars bound in every row). This handles cases like `not-join [?u ?r]` where the + // body only binds `?r`. // // Values are normalized: Value::Keyword(k) that represents an entity keyword is // converted to Value::Ref(uuid) so that probe keys from the outer binding (which // may store entity references as keywords) match the body bindings (which bind - // entity fields as Value::Ref). - let not_join_exclusion_sets: Vec, HashSet>)>> = + // entity fields as Value::Ref). `has_expr` is computed once here, not per-binding. + let not_join_exclusion_sets: Vec, HashSet>)>> = not_join_clauses .iter() .map(|(join_vars, nj_clauses)| { + let has_expr = nj_clauses + .iter() + .any(|c| matches!(c, WhereClause::Expr { .. })); let patterns: Vec<_> = nj_clauses .iter() .filter_map(|c| match c { @@ -628,18 +641,16 @@ impl DatalogExecutor { if body_bindings.is_empty() { // No body bindings → no exclusions. Use empty exclusion set with // all join_vars as key so probe returns not-found for all. - return Some((join_vars.clone(), HashSet::new())); + return Some((has_expr, join_vars.clone(), HashSet::new())); } - // Determine which join_vars actually appear in body bindings. - // Only those can be used as the exclusion key. - let key_vars: Vec = { - let sample = &body_bindings[0]; - join_vars - .iter() - .filter(|v| sample.contains_key(*v)) - .cloned() - .collect() - }; + // Determine which join_vars appear in ALL body binding rows. + // Using only the first row (as before) misses variables that appear + // in later rows but not the first when results are heterogeneous. + let key_vars: Vec = join_vars + .iter() + .filter(|v| body_bindings.iter().all(|b| b.contains_key(*v))) + .cloned() + .collect(); // Project to key_vars only (subset of join_vars), normalizing values. let exclusion_set: HashSet> = body_bindings .into_iter() @@ -654,7 +665,7 @@ impl DatalogExecutor { kv }) .collect(); - Some((key_vars, exclusion_set)) + Some((has_expr, key_vars, exclusion_set)) }) .collect(); @@ -663,32 +674,43 @@ impl DatalogExecutor { .filter(|binding| { // Check not-bodies via pre-computed exclusion sets (fast path) or // via not_body_matches (slow path for expr-only bodies). - for (i, not_body) in not_clauses.iter().enumerate() { - match ¬_exclusion_sets[i] { - Some(exclusion_set) => { - let has_expr = not_body - .iter() - .any(|c| matches!(c, WhereClause::Expr { .. })); + for (not_body, exclusion_entry) in + not_clauses.iter().zip(not_exclusion_sets.iter()) + { + match exclusion_entry { + Some((has_expr, exclusion_set)) => { if exclusion_set.is_empty() && !has_expr { // No excluding bindings → this outer binding is safe. continue; } if !has_expr { // Fast path: probe exclusion set using the outer binding's - // values for the join variables. + // values for the join variables, normalized for consistency. if let Some(sample) = exclusion_set.iter().next() { let key: Vec<(String, Value)> = sample .iter() .filter_map(|(var, _)| { binding .get(var) - .map(|val| (var.clone(), val.clone())) + .map(|val| (var.clone(), normalize_value(val))) }) .collect(); - // Only probe if all join vars are bound in the outer binding. - if key.len() == sample.len() - && exclusion_set.contains(&key) - { + if key.len() == sample.len() { + // All join vars are bound in the outer binding. + if exclusion_set.contains(&key) { + return false; + } + continue; + } + // Outer binding is underspecified (fewer vars than + // the exclusion set key) — fall back to slow path. + if not_body_matches( + not_body, + binding, + filtered_facts.clone(), + valid_at_value.clone(), + ®istry, + ) { return false; } continue; @@ -721,12 +743,11 @@ impl DatalogExecutor { } // Check not-join-bodies. - for (i, (join_vars, nj_clauses)) in not_join_clauses.iter().enumerate() { - match ¬_join_exclusion_sets[i] { - Some((key_vars, exclusion_set)) => { - let has_expr = nj_clauses - .iter() - .any(|c| matches!(c, WhereClause::Expr { .. })); + for ((join_vars, nj_clauses), nj_exclusion_entry) in + not_join_clauses.iter().zip(not_join_exclusion_sets.iter()) + { + match nj_exclusion_entry { + Some((has_expr, key_vars, exclusion_set)) => { if !has_expr { if key_vars.is_empty() { // Body bound no join vars: if exclusion set non-empty, From 5e0a3e61454791af7807cd26e8132e069ad3a386 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 15 May 2026 13:42:45 +0530 Subject: [PATCH 3/9] fix: not-join underspecified binding now falls back to evaluate_not_join (#202) --- src/query/datalog/executor.rs | 18 +++++++++++++++--- 1 file changed, 15 insertions(+), 3 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index c5429c6b7e..7071f0c13e 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -768,9 +768,21 @@ impl DatalogExecutor { }) .collect(); key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); - if key.len() == key_vars.len() - && exclusion_set.contains(&key) - { + if key.len() == key_vars.len() { + if exclusion_set.contains(&key) { + return false; + } + continue; + } + // Outer binding underspecified relative to the not-join body — + // fall back to the slow path so the body is correctly evaluated. + if evaluate_not_join( + join_vars, + nj_clauses, + binding, + filtered_facts.clone(), + ®istry, + ) { return false; } continue; From c38c73d6bcec89ce623a8184a61d1d76b4e6f1f3 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 15 May 2026 13:54:33 +0530 Subject: [PATCH 4/9] =?UTF-8?q?perf:=20empty-seed=20branch=20eval=20in=20a?= =?UTF-8?q?pply=5For=5Fclauses=20=E2=80=94=20O(N=C2=B2)=20=E2=86=92=20O(N)?= =?UTF-8?q?=20(#203)?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit For Or/OrJoin branches that contain only patterns (no Not/NotJoin), evaluate each branch once from an empty seed to get the full candidate set, then hash-join the union back onto incoming bindings using shared user-visible variables. Branches with Not/NotJoin fall back to the classic seeded evaluation to preserve correctness (those clauses need bound outer-scope variables). Adds or_hash_join_tests covering the no-overlap, overlap deduplication, and or-join cases. Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/executor.rs | 305 +++++++++++++++++++++++++++++++--- 1 file changed, 285 insertions(+), 20 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 7071f0c13e..fd2c3039f3 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -1744,13 +1744,58 @@ pub(crate) fn apply_or_clauses( for clause in clauses { match clause { WhereClause::Or(branches) => { - let mut seen: std::collections::HashSet> = + // If any branch contains Not/NotJoin clauses (which need bound variables + // from the outer scope to evaluate correctly), fall back to the classic + // seeded-branch evaluation to preserve correctness. + let any_branch_has_not = branches.iter().any(|b| { + b.iter().any(|c| { + matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. }) + }) + }); + + if any_branch_has_not { + // Classic O(N·B) seeded evaluation: each incoming binding seeds each branch. + let mut seen: std::collections::HashSet> = + std::collections::HashSet::new(); + let mut result: Vec = Vec::new(); + for branch in branches { + let branch_result = evaluate_branch( + branch, + bindings.clone(), + storage.clone(), + rules, + as_of.clone(), + valid_at.clone(), + registry, + )?; + for b in branch_result { + let mut key: Vec<_> = b + .iter() + .filter(|(k, _)| !k.starts_with("__")) + .map(|(k, v)| (k.clone(), v.clone())) + .collect(); + key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + if seen.insert(key) { + result.push(b); + } + } + } + bindings = result; + continue; + } + + // Fast path: no Not/NotJoin in any branch. + // Evaluate every branch from an empty seed (independent of incoming bindings), + // then hash-join the union back onto incoming bindings on shared variables. + let empty_seed: Vec = vec![HashMap::new()]; + let mut union_bindings: Vec = Vec::new(); + let mut seen_keys: std::collections::HashSet> = std::collections::HashSet::new(); - let mut result: Vec = Vec::new(); + for branch in branches { let branch_result = evaluate_branch( branch, - bindings.clone(), + empty_seed.clone(), storage.clone(), rules, as_of.clone(), @@ -1758,31 +1803,96 @@ pub(crate) fn apply_or_clauses( registry, )?; for b in branch_result { - let mut key: Vec<_> = - b.iter().map(|(k, v)| (k.clone(), v.clone())).collect(); - key.sort_unstable(); - if seen.insert(key) { - result.push(b); + // Deduplicate on user-visible variables only (exclude internal `__` keys). + let mut key: Vec<_> = b + .iter() + .filter(|(k, _)| !k.starts_with("__")) + .map(|(k, v)| (k.clone(), v.clone())) + .collect(); + key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + if seen_keys.insert(key) { + union_bindings.push(b); + } + } + } + + // Determine shared variable names: variables present in both + // incoming bindings and branch results. + // Exclude internal metadata keys (prefixed with `__`) — those are + // fact-specific and differ between patterns for the same entity. + let branch_var_names: std::collections::HashSet<&str> = union_bindings + .iter() + .flat_map(|b| b.keys().map(|k| k.as_str())) + .filter(|k| !k.starts_with("__")) + .collect(); + let shared_vars: Vec = bindings + .iter() + .flat_map(|b| b.keys().cloned()) + .collect::>() + .into_iter() + .filter(|v| !v.starts_with("__") && branch_var_names.contains(v.as_str())) + .collect(); + + if shared_vars.is_empty() { + // No shared variables → replace bindings with branch union entirely. + bindings = union_bindings; + continue; + } + + // Build HashMap: shared-key tuple → Vec + let mut branch_map: HashMap, Vec> = HashMap::new(); + for b in union_bindings { + let key: Vec<(String, Value)> = shared_vars + .iter() + .filter_map(|v| b.get(v).map(|val| (v.clone(), val.clone()))) + .collect(); + branch_map.entry(key).or_default().push(b); + } + + // For each incoming binding, look up matching branch results and merge. + let mut result: Vec = Vec::new(); + let mut seen_result: std::collections::HashSet> = + std::collections::HashSet::new(); + for incoming in &bindings { + let key: Vec<(String, Value)> = shared_vars + .iter() + .filter_map(|v| incoming.get(v).map(|val| (v.clone(), val.clone()))) + .collect(); + if let Some(matches) = branch_map.get(&key) { + for branch_binding in matches { + // Merge: start with incoming, extend with branch-introduced vars. + let mut merged = incoming.clone(); + for (k, v) in branch_binding { + merged.entry(k.clone()).or_insert_with(|| v.clone()); + } + let mut dedup_key: Vec<_> = + merged.iter().map(|(k, v)| (k.clone(), v.clone())).collect(); + dedup_key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + if seen_result.insert(dedup_key) { + result.push(merged); + } } } } bindings = result; } + WhereClause::OrJoin { join_vars, branches, } => { - // outer_keys: all variable names present in the incoming bindings let outer_keys: std::collections::HashSet = bindings.iter().flat_map(|b| b.keys().cloned()).collect(); - let mut seen: std::collections::HashSet> = + let empty_seed: Vec = vec![HashMap::new()]; + let mut projected: Vec = Vec::new(); + let mut seen_proj: std::collections::HashSet> = std::collections::HashSet::new(); - let mut result: Vec = Vec::new(); + for branch in branches { let branch_result = evaluate_branch( branch, - bindings.clone(), + empty_seed.clone(), storage.clone(), rules, as_of.clone(), @@ -1790,23 +1900,56 @@ pub(crate) fn apply_or_clauses( registry, )?; for mut b in branch_result { - // Drop partial bindings (missing any join_var) if !join_vars.iter().all(|v| b.contains_key(v)) { continue; } - // Project to outer_keys (all variables bound before this or-join clause). - // This is equivalent to retaining join_vars because: - // (1) the parser enforces join_vars ⊆ outer_bound, so join_vars ⊆ outer_keys, and - // (2) retaining outer_keys is safe because those variables were stable before the or-join. + // Project to outer_keys (preserves join_vars since join_vars ⊆ outer_keys) b.retain(|k, _| outer_keys.contains(k)); - let key: Vec<_> = b.iter().map(|(k, v)| (k.clone(), v.clone())).collect(); - if seen.insert(key) { - result.push(b); + let mut key: Vec<_> = + b.iter().map(|(k, v)| (k.clone(), v.clone())).collect(); + key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + if seen_proj.insert(key) { + projected.push(b); + } + } + } + + // Build HashMap keyed on join_vars tuple. + let mut branch_map: HashMap, Vec> = HashMap::new(); + for b in projected { + let key: Vec<(String, Value)> = join_vars + .iter() + .filter_map(|v| b.get(v).map(|val| (v.clone(), val.clone()))) + .collect(); + branch_map.entry(key).or_default().push(b); + } + + let mut result: Vec = Vec::new(); + let mut seen_result: std::collections::HashSet> = + std::collections::HashSet::new(); + for incoming in &bindings { + let key: Vec<(String, Value)> = join_vars + .iter() + .filter_map(|v| incoming.get(v).map(|val| (v.clone(), val.clone()))) + .collect(); + if let Some(matches) = branch_map.get(&key) { + for branch_binding in matches { + let mut merged = incoming.clone(); + for (k, v) in branch_binding { + merged.entry(k.clone()).or_insert_with(|| v.clone()); + } + let mut dedup_key: Vec<_> = + merged.iter().map(|(k, v)| (k.clone(), v.clone())).collect(); + dedup_key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + if seen_result.insert(dedup_key) { + result.push(merged); + } } } } bindings = result; } + _ => {} // Other clause types handled elsewhere } } @@ -5052,3 +5195,125 @@ mod not_hash_join_tests { } } } + +#[cfg(test)] +mod or_hash_join_tests { + use crate::graph::FactStorage; + use crate::query::datalog::executor::DatalogExecutor; + + + fn make_or_db(n: usize, a_count: usize, b_count: usize) -> DatalogExecutor { + let storage = FactStorage::new(); + let exec = DatalogExecutor::new(storage); + for batch_start in (0..n).step_by(100) { + let batch_end = (batch_start + 100).min(n); + let mut cmd = String::from("(transact ["); + for i in batch_start..batch_end { + cmd.push_str(&format!("[:e{i} :val {i}]", i = i)); + } + cmd.push_str("])"); + exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()).unwrap(); + } + for batch_start in (0..a_count).step_by(100) { + let batch_end = (batch_start + 100).min(a_count); + let mut cmd = String::from("(transact ["); + for i in batch_start..batch_end { + cmd.push_str(&format!("[:e{i} :tag-a true]", i = i)); + } + cmd.push_str("])"); + exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()).unwrap(); + } + let b_start = n.saturating_sub(b_count); + for batch_start in (b_start..n).step_by(100) { + let batch_end = (batch_start + 100).min(n); + let mut cmd = String::from("(transact ["); + for i in batch_start..batch_end { + cmd.push_str(&format!("[:e{i} :tag-b true]", i = i)); + } + cmd.push_str("])"); + exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()).unwrap(); + } + exec + } + + #[test] + fn or_clause_returns_correct_count() { + // 1000 entities, first 250 have :tag-a, last 250 have :tag-b, no overlap + let n = 1_000; + let a = n / 4; + let b = n / 4; + let exec = make_or_db(n, a, b); + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?e :where [?e :val ?v] \ + (or [?e :tag-a true] [?e :tag-b true])])", + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result + { + assert_eq!( + results.len(), + a + b, + "expected {} results from or (a={} b={} no overlap)", + a + b, + a, + b + ); + } else { + panic!("expected QueryResults"); + } + } + + #[test] + fn or_join_clause_returns_correct_count() { + let n = 1_000; + let a = n / 4; + let b = n / 4; + let exec = make_or_db(n, a, b); + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?e :where [?e :val ?v] \ + (or-join [?e] [?e :tag-a true] [?e :tag-b true])])", + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result + { + assert_eq!( + results.len(), + a + b, + "expected {} results from or-join", + a + b + ); + } else { + panic!("expected QueryResults"); + } + } + + #[test] + fn or_clause_with_overlap_deduplicates() { + // 100 entities, all have both :tag-a and :tag-b → result should be 100, not 200 + let n = 100; + let exec = make_or_db(n, n, n); + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?e :where [?e :val ?v] \ + (or [?e :tag-a true] [?e :tag-b true])])", + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result + { + assert_eq!(results.len(), n, "expected {} deduplicated results", n); + } else { + panic!("expected QueryResults"); + } + } +} From 99171fd7430bc17e8e5a2a1833f5cc67d98d244a Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 15 May 2026 13:59:10 +0530 Subject: [PATCH 5/9] fix: add defensive guard and clarifying comment in apply_or_clauses (#203) --- src/query/datalog/executor.rs | 23 ++++++++++++++++++++++- 1 file changed, 22 insertions(+), 1 deletion(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index fd2c3039f3..e8d8527f3a 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -1834,7 +1834,16 @@ pub(crate) fn apply_or_clauses( .collect(); if shared_vars.is_empty() { - // No shared variables → replace bindings with branch union entirely. + // No shared user-visible variables between incoming bindings and branch + // results. This is semantically equivalent to a cross-join, which only + // makes sense when `bindings` carries no meaningful state yet (i.e. it + // is a single empty binding — the query start state — or all incoming + // variables are fact-metadata keys that the branch does not reference). + // In that case the cross-join degenerates to "replace with branch union", + // which is what the original seeded evaluation produced. Incoming bindings + // that carry user-visible variables but none matching any branch variable + // would be silently dropped here — that situation should not arise given + // that `or` must share at least one variable with the surrounding clause. bindings = union_bindings; continue; } @@ -1884,6 +1893,18 @@ pub(crate) fn apply_or_clauses( let outer_keys: std::collections::HashSet = bindings.iter().flat_map(|b| b.keys().cloned()).collect(); + // Defensive check: every join_var must be bound in the incoming scope. + // The parser validates this, but guard here to avoid silent wrong results + // if a join_var is missing from outer_keys (hash-join key would be partial). + for jv in join_vars.iter() { + if !outer_keys.contains(jv.as_str()) { + anyhow::bail!( + "or-join variable {} is not bound in the incoming scope", + jv + ); + } + } + let empty_seed: Vec = vec![HashMap::new()]; let mut projected: Vec = Vec::new(); let mut seen_proj: std::collections::HashSet> = From 729b7af8307ac47189b8d196d26cb225af86ed80 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 15 May 2026 14:09:49 +0530 Subject: [PATCH 6/9] =?UTF-8?q?perf:=20hash-join=20in=20join=5Fwith=5Fpatt?= =?UTF-8?q?ern=20=E2=80=94=20O(N=C2=B2)=20=E2=86=92=20O(N)=20(#204)?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Replace the nested-loop in join_with_pattern with a hash-join when a shared join variable is detected in the entity or value position of the incoming pattern. Keyword/Ref values are normalized during build and probe so cross-type entity references (e.g., Value::Keyword stored as a fact value vs. Value::Ref produced in entity position) compare equal. The fallback to nested-loop is preserved for pseudo-attribute patterns and patterns with no shared variable. Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/matcher.rs | 245 ++++++++++++++++++++++++++++++++++- 1 file changed, 238 insertions(+), 7 deletions(-) diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index aea969a185..e324079c8e 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -391,24 +391,156 @@ impl PatternMatcher { results } - /// Join existing bindings with a new pattern - /// Only keeps bindings that are consistent with the new pattern + /// Join existing bindings with a new pattern. + /// + /// Uses a hash-join when the pattern shares a variable with existing bindings + /// (the common `?e`-join shape). Falls back to the nested-loop scan when no + /// shared join variable is found (unrelated patterns, fully-literal patterns, + /// or pseudo-attribute patterns which have their own fast path in + /// `match_pattern_with_bindings`). fn join_with_pattern( &self, existing_bindings: Vec, pattern: &Pattern, ) -> Vec { - let mut results = Vec::new(); + if existing_bindings.is_empty() { + return vec![]; + } - for existing in existing_bindings { - // Try to match the pattern with existing bindings - let new_matches = self.match_pattern_with_bindings(pattern, &existing); - results.extend(new_matches); + // Detect the join variable: the first variable in entity, then value position + // of the new pattern that also appears as a bound key in the existing bindings. + // We skip pseudo-attributes (they have a dedicated fast path in + // match_pattern_with_bindings) and fully-literal patterns (nested loop is + // already O(1) per binding for those). + let is_pseudo = matches!(&pattern.attribute, AttributeSpec::Pseudo(_)); + + let join_var: Option = if is_pseudo { + None + } else { + // Check entity position first. + let entity_var = match &pattern.entity { + EdnValue::Symbol(s) if s.starts_with('?') => { + // It's a variable. Is it bound in existing bindings? + if existing_bindings + .first() + .map_or(false, |b| b.contains_key(s)) + { + Some(s.clone()) + } else { + None + } + } + _ => None, + }; + if entity_var.is_some() { + entity_var + } else { + // Check value position. + match &pattern.value { + EdnValue::Symbol(s) if s.starts_with('?') => { + if existing_bindings + .first() + .map_or(false, |b| b.contains_key(s)) + { + Some(s.clone()) + } else { + None + } + } + _ => None, + } + } + }; + + let Some(jvar) = join_var else { + // No join variable detected: fall back to nested-loop scan. + let mut results = Vec::new(); + for existing in existing_bindings { + let new_matches = self.match_pattern_with_bindings(pattern, &existing); + results.extend(new_matches); + } + return results; + }; + + // Hash-join path: + // 1. Scan all candidate facts for this pattern from an empty binding (no outer context). + // This gives us every binding the pattern can produce, keyed by the join variable. + let candidate_bindings = self.match_pattern(&pattern.clone()); + + // 2. Build HashMap: join_var_value → Vec + // Normalize keyword values to Ref (UUID) so keyword entity references + // (e.g., Value::Keyword(":d-bad") stored as a value) can match the UUID + // that match_fact_against_pattern produces when the same entity appears + // in entity position (stored as Value::Ref). This mirrors the cross-type + // matching done by match_component's EdnValue::Keyword arm. + let mut build_side: HashMap> = HashMap::new(); + for b in candidate_bindings { + if let Some(val) = b.get(&jvar) { + let key = Self::normalize_join_value(val); + build_side.entry(key).or_default().push(b); + } } + // 3. Probe: for each existing binding, look up join_var value. + let mut results = Vec::new(); + for existing in existing_bindings { + let Some(probe_val) = existing.get(&jvar) else { + // Outer binding doesn't have the join var yet — fall back to scan for this row. + let new_matches = self.match_pattern_with_bindings(pattern, &existing); + results.extend(new_matches); + continue; + }; + let probe_key = Self::normalize_join_value(probe_val); + if let Some(matches) = build_side.get(&probe_key) { + for candidate in matches { + // Merge and consistency-check. + let mut merged = existing.clone(); + let mut consistent = true; + for (var, val) in candidate { + if var.starts_with("__f") { + merged.insert(var.clone(), val.clone()); + continue; + } + if let Some(existing_val) = existing.get(var) { + // Compare using normalized values so that keyword entity + // references (e.g., Keyword(":d-bad") stored as a value in + // one fact) are treated as equal to the UUID Ref produced + // when the same entity appears in entity position. + if Self::normalize_join_value(existing_val) + != Self::normalize_join_value(val) + { + consistent = false; + break; + } + } else { + merged.insert(var.clone(), val.clone()); + } + } + if consistent { + results.push(merged); + } + } + } + // No match in build side → this outer binding is dropped (inner join semantics). + } results } + /// Normalize a value for use as a hash-join key. + /// + /// Converts `Value::Keyword` to `Value::Ref` when the keyword can be parsed + /// as a UUID or resolved via the deterministic UUID-v5 scheme. This ensures + /// that a keyword entity reference (e.g., `:d-bad` stored as a value) and the + /// same entity stored as a Ref in entity position compare equal in the HashMap. + fn normalize_join_value(val: &Value) -> Value { + if let Value::Keyword(k) = val { + if let Ok(uuid) = edn_to_entity_id(&EdnValue::Keyword(k.clone())) { + return Value::Ref(uuid); + } + } + val.clone() + } + /// Match a pattern given existing variable bindings /// Returns new bindings that extend the existing ones fn match_pattern_with_bindings(&self, pattern: &Pattern, existing: &Bindings) -> Vec { @@ -1199,3 +1331,102 @@ mod tests { ); } } + +#[cfg(test)] +mod hash_join_tests { + use crate::graph::FactStorage; + use crate::query::datalog::executor::DatalogExecutor; + + fn make_join_db(n: usize, dept_count: usize) -> DatalogExecutor { + let storage = FactStorage::new(); + let exec = DatalogExecutor::new(storage); + for batch_start in (0..n).step_by(50) { + let batch_end = (batch_start + 50).min(n); + let mut cmd = String::from("(transact ["); + for i in batch_start..batch_end { + cmd.push_str(&format!("[:e{i} :val {i}]", i = i)); + cmd.push_str(&format!("[:e{i} :dept :d{d}]", i = i, d = i % dept_count)); + } + cmd.push_str("])"); + exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()) + .unwrap(); + } + exec + } + + /// Two-pattern join: every entity has both :dept and :val facts. + /// Querying [:find ?e ?dept ?v :where [?e :dept ?dept] [?e :val ?v]] should + /// return exactly one row per entity (N rows for N entities). + #[test] + fn two_pattern_join_returns_correct_count() { + let n = 100; + let exec = make_join_db(n, 10); + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?e ?dept ?v :where [?e :dept ?dept] [?e :val ?v]])", + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result + { + // One row per entity — the join must not produce a cross-product. + assert_eq!(results.len(), n, "expected one row per entity"); + } else { + panic!("expected QueryResults"); + } + } + + /// Correctness check: for 10 entities across 2 departments, the join must + /// pair each entity with the right department and value (no mixing). + #[test] + fn two_pattern_join_values_are_correct() { + // e0,e2,e4,e6,e8 → :d0; e1,e3,e5,e7,e9 → :d1 + let n = 10; + let exec = make_join_db(n, 2); + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?e ?dept ?v :where [?e :dept ?dept] [?e :val ?v]])", + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { + vars, results, .. + } = result + { + assert_eq!(results.len(), n, "expected one row per entity"); + let dept_idx = vars.iter().position(|v| v == "?dept").expect("?dept in vars"); + let val_idx = vars.iter().position(|v| v == "?v").expect("?v in vars"); + // Collect (dept, val) pairs; no entity should appear in both departments. + let mut d0_vals: Vec = Vec::new(); + let mut d1_vals: Vec = Vec::new(); + for row in &results { + if let ( + crate::graph::types::Value::Keyword(dept), + crate::graph::types::Value::Integer(val), + ) = (&row[dept_idx], &row[val_idx]) + { + if dept == ":d0" { + d0_vals.push(*val); + } else if dept == ":d1" { + d1_vals.push(*val); + } + } + } + assert_eq!(d0_vals.len(), 5, "d0 should have 5 entities"); + assert_eq!(d1_vals.len(), 5, "d1 should have 5 entities"); + // All d0 vals are even (0,2,4,6,8) and d1 vals are odd (1,3,5,7,9). + for v in &d0_vals { + assert_eq!(v % 2, 0, "d0 entities have even vals"); + } + for v in &d1_vals { + assert_eq!(v % 2, 1, "d1 entities have odd vals"); + } + } else { + panic!("expected QueryResults"); + } + } +} From d5f491565940e2dc94e8d7ad80575242db32059c Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 15 May 2026 14:14:07 +0530 Subject: [PATCH 7/9] fix: address code review issues in join_with_pattern (#204) Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/matcher.rs | 29 +++++++++++++++-------------- 1 file changed, 15 insertions(+), 14 deletions(-) diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index e324079c8e..293082e3ab 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -423,7 +423,7 @@ impl PatternMatcher { // It's a variable. Is it bound in existing bindings? if existing_bindings .first() - .map_or(false, |b| b.contains_key(s)) + .is_some_and(|b| b.contains_key(s)) { Some(s.clone()) } else { @@ -440,7 +440,7 @@ impl PatternMatcher { EdnValue::Symbol(s) if s.starts_with('?') => { if existing_bindings .first() - .map_or(false, |b| b.contains_key(s)) + .is_some_and(|b| b.contains_key(s)) { Some(s.clone()) } else { @@ -465,7 +465,7 @@ impl PatternMatcher { // Hash-join path: // 1. Scan all candidate facts for this pattern from an empty binding (no outer context). // This gives us every binding the pattern can produce, keyed by the join variable. - let candidate_bindings = self.match_pattern(&pattern.clone()); + let candidate_bindings = self.match_pattern(pattern); // 2. Build HashMap: join_var_value → Vec // Normalize keyword values to Ref (UUID) so keyword entity references @@ -501,12 +501,12 @@ impl PatternMatcher { merged.insert(var.clone(), val.clone()); continue; } - if let Some(existing_val) = existing.get(var) { + if let Some(merged_val) = merged.get(var) { // Compare using normalized values so that keyword entity // references (e.g., Keyword(":d-bad") stored as a value in // one fact) are treated as equal to the UUID Ref produced // when the same entity appears in entity position. - if Self::normalize_join_value(existing_val) + if Self::normalize_join_value(merged_val) != Self::normalize_join_value(val) { consistent = false; @@ -526,17 +526,18 @@ impl PatternMatcher { results } - /// Normalize a value for use as a hash-join key. + /// Normalize a binding value for use as a hash-join key. /// - /// Converts `Value::Keyword` to `Value::Ref` when the keyword can be parsed - /// as a UUID or resolved via the deterministic UUID-v5 scheme. This ensures - /// that a keyword entity reference (e.g., `:d-bad` stored as a value) and the - /// same entity stored as a Ref in entity position compare equal in the HashMap. + /// Converts `Value::Keyword(k)` → `Value::Ref(uuid)` so that entity references + /// bound via keyword (value position) and via entity ID (entity position) hash + /// to the same key. Used only for key comparison — does NOT affect what is + /// stored in merged output bindings (the original `val` is always inserted into + /// the result binding, never the normalized form). fn normalize_join_value(val: &Value) -> Value { - if let Value::Keyword(k) = val { - if let Ok(uuid) = edn_to_entity_id(&EdnValue::Keyword(k.clone())) { - return Value::Ref(uuid); - } + if let Value::Keyword(k) = val + && let Ok(uuid) = edn_to_entity_id(&EdnValue::Keyword(k.clone())) + { + return Value::Ref(uuid); } val.clone() } From 447cc679349f28d83a23b385d9df8441dd87ba48 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 15 May 2026 14:37:51 +0530 Subject: [PATCH 8/9] fix: type aliases to satisfy clippy::type_complexity (#202) --- src/query/datalog/executor.rs | 117 +++++++++++++++++----------------- 1 file changed, 58 insertions(+), 59 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index e8d8527f3a..8a1f345091 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -562,7 +562,7 @@ impl DatalogExecutor { // Each element: either Some((has_expr, HashSet of excluded join-key tuples)) or None // (expr-only, use slow path). `has_expr` is computed once here during pre-compute, // not inside the per-binding filter closure. - let not_exclusion_sets: Vec>)>> = not_clauses + let not_exclusion_sets: Vec = not_clauses .iter() .map(|not_body| { let has_expr = not_body @@ -579,11 +579,10 @@ impl DatalogExecutor { // Expr-only body: no pre-computation possible. return None; } - let matcher = - PatternMatcher::from_slice_with_valid_at( - filtered_facts.clone(), - valid_at_value.clone(), - ); + let matcher = PatternMatcher::from_slice_with_valid_at( + filtered_facts.clone(), + valid_at_value.clone(), + ); let body_bindings = matcher.match_patterns(&patterns); // Store all body bindings as sorted (key, value) vecs for probing. // Normalize values (e.g. keyword entities → Ref) so that probe keys from @@ -615,59 +614,51 @@ impl DatalogExecutor { // converted to Value::Ref(uuid) so that probe keys from the outer binding (which // may store entity references as keywords) match the body bindings (which bind // entity fields as Value::Ref). `has_expr` is computed once here, not per-binding. - let not_join_exclusion_sets: Vec, HashSet>)>> = - not_join_clauses - .iter() - .map(|(join_vars, nj_clauses)| { - let has_expr = nj_clauses - .iter() - .any(|c| matches!(c, WhereClause::Expr { .. })); - let patterns: Vec<_> = nj_clauses - .iter() - .filter_map(|c| match c { - WhereClause::Pattern(p) => Some(p.clone()), - _ => None, - }) - .collect(); - if patterns.is_empty() { - return None; - } - let matcher = - PatternMatcher::from_slice_with_valid_at( - filtered_facts.clone(), - valid_at_value.clone(), - ); - let body_bindings = matcher.match_patterns(&patterns); - if body_bindings.is_empty() { - // No body bindings → no exclusions. Use empty exclusion set with - // all join_vars as key so probe returns not-found for all. - return Some((has_expr, join_vars.clone(), HashSet::new())); - } - // Determine which join_vars appear in ALL body binding rows. - // Using only the first row (as before) misses variables that appear - // in later rows but not the first when results are heterogeneous. - let key_vars: Vec = join_vars - .iter() - .filter(|v| body_bindings.iter().all(|b| b.contains_key(*v))) - .cloned() - .collect(); - // Project to key_vars only (subset of join_vars), normalizing values. - let exclusion_set: HashSet> = body_bindings - .into_iter() - .map(|b| { - let mut kv: Vec<(String, Value)> = key_vars - .iter() - .filter_map(|v| { - b.get(v).map(|val| (v.clone(), normalize_value(val))) - }) - .collect(); - kv.sort_unstable_by(|a, b| a.0.cmp(&b.0)); - kv - }) - .collect(); - Some((has_expr, key_vars, exclusion_set)) - }) - .collect(); + let not_join_exclusion_sets: Vec = not_join_clauses + .iter() + .map(|(join_vars, nj_clauses)| { + let has_expr = nj_clauses + .iter() + .any(|c| matches!(c, WhereClause::Expr { .. })); + let patterns: Vec<_> = nj_clauses + .iter() + .filter_map(|c| match c { + WhereClause::Pattern(p) => Some(p.clone()), + _ => None, + }) + .collect(); + if patterns.is_empty() { + return None; + } + let matcher = PatternMatcher::from_slice_with_valid_at( + filtered_facts.clone(), + valid_at_value.clone(), + ); + let body_bindings = matcher.match_patterns(&patterns); + if body_bindings.is_empty() { + return Some((has_expr, join_vars.clone(), HashSet::new())); + } + let key_vars: Vec = join_vars + .iter() + .filter(|v| body_bindings.iter().all(|b| b.contains_key(*v))) + .cloned() + .collect(); + let exclusion_set: HashSet> = body_bindings + .into_iter() + .map(|b| { + let mut kv: Vec<(String, Value)> = key_vars + .iter() + .filter_map(|v| { + b.get(v).map(|val| (v.clone(), normalize_value(val))) + }) + .collect(); + kv.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + kv + }) + .collect(); + Some((has_expr, key_vars, exclusion_set)) + }) + .collect(); bindings .into_iter() @@ -1249,6 +1240,14 @@ fn extract_variables( } type Binding = std::collections::HashMap; +/// Internal type alias for pre-computed not-body exclusion sets. +type NotExclusionEntry = Option<(bool, std::collections::HashSet>)>; +/// Internal type alias for pre-computed not-join exclusion sets. +type NotJoinExclusionEntry = Option<( + bool, + Vec, + std::collections::HashSet>, +)>; /// Unified post-processing: handles plain-variable extraction, aggregation, /// window functions, and mixed (aggregate + window) queries. From 92b2ce4b080991adb69f4fadd6bf3855e0b31313 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 15 May 2026 14:47:38 +0530 Subject: [PATCH 9/9] style: apply rustfmt formatting after rebase --- src/query/datalog/executor.rs | 35 ++++++++++++++--------------------- src/query/datalog/matcher.rs | 18 +++++++----------- 2 files changed, 21 insertions(+), 32 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 8a1f345091..fff2de2308 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -1747,9 +1747,8 @@ pub(crate) fn apply_or_clauses( // from the outer scope to evaluate correctly), fall back to the classic // seeded-branch evaluation to preserve correctness. let any_branch_has_not = branches.iter().any(|b| { - b.iter().any(|c| { - matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. }) - }) + b.iter() + .any(|c| matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. })) }); if any_branch_has_not { @@ -1897,10 +1896,7 @@ pub(crate) fn apply_or_clauses( // if a join_var is missing from outer_keys (hash-join key would be partial). for jv in join_vars.iter() { if !outer_keys.contains(jv.as_str()) { - anyhow::bail!( - "or-join variable {} is not bound in the incoming scope", - jv - ); + anyhow::bail!("or-join variable {} is not bound in the incoming scope", jv); } } @@ -5147,8 +5143,7 @@ mod not_hash_join_tests { .unwrap(), ) .unwrap(); - if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result - { + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { assert_eq!( results.len(), n - excluded, @@ -5202,8 +5197,7 @@ mod not_hash_join_tests { .unwrap(), ) .unwrap(); - if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result - { + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { assert_eq!( results.len(), n - excluded, @@ -5221,7 +5215,6 @@ mod or_hash_join_tests { use crate::graph::FactStorage; use crate::query::datalog::executor::DatalogExecutor; - fn make_or_db(n: usize, a_count: usize, b_count: usize) -> DatalogExecutor { let storage = FactStorage::new(); let exec = DatalogExecutor::new(storage); @@ -5232,7 +5225,8 @@ mod or_hash_join_tests { cmd.push_str(&format!("[:e{i} :val {i}]", i = i)); } cmd.push_str("])"); - exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()).unwrap(); + exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()) + .unwrap(); } for batch_start in (0..a_count).step_by(100) { let batch_end = (batch_start + 100).min(a_count); @@ -5241,7 +5235,8 @@ mod or_hash_join_tests { cmd.push_str(&format!("[:e{i} :tag-a true]", i = i)); } cmd.push_str("])"); - exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()).unwrap(); + exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()) + .unwrap(); } let b_start = n.saturating_sub(b_count); for batch_start in (b_start..n).step_by(100) { @@ -5251,7 +5246,8 @@ mod or_hash_join_tests { cmd.push_str(&format!("[:e{i} :tag-b true]", i = i)); } cmd.push_str("])"); - exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()).unwrap(); + exec.execute(crate::query::datalog::parser::parse_datalog_command(&cmd).unwrap()) + .unwrap(); } exec } @@ -5272,8 +5268,7 @@ mod or_hash_join_tests { .unwrap(), ) .unwrap(); - if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result - { + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { assert_eq!( results.len(), a + b, @@ -5302,8 +5297,7 @@ mod or_hash_join_tests { .unwrap(), ) .unwrap(); - if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result - { + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { assert_eq!( results.len(), a + b, @@ -5329,8 +5323,7 @@ mod or_hash_join_tests { .unwrap(), ) .unwrap(); - if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result - { + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { assert_eq!(results.len(), n, "expected {} deduplicated results", n); } else { panic!("expected QueryResults"); diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index 293082e3ab..63963d9c99 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -421,10 +421,7 @@ impl PatternMatcher { let entity_var = match &pattern.entity { EdnValue::Symbol(s) if s.starts_with('?') => { // It's a variable. Is it bound in existing bindings? - if existing_bindings - .first() - .is_some_and(|b| b.contains_key(s)) - { + if existing_bindings.first().is_some_and(|b| b.contains_key(s)) { Some(s.clone()) } else { None @@ -438,10 +435,7 @@ impl PatternMatcher { // Check value position. match &pattern.value { EdnValue::Symbol(s) if s.starts_with('?') => { - if existing_bindings - .first() - .is_some_and(|b| b.contains_key(s)) - { + if existing_bindings.first().is_some_and(|b| b.contains_key(s)) { Some(s.clone()) } else { None @@ -1370,8 +1364,7 @@ mod hash_join_tests { .unwrap(), ) .unwrap(); - if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result - { + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { // One row per entity — the join must not produce a cross-product. assert_eq!(results.len(), n, "expected one row per entity"); } else { @@ -1399,7 +1392,10 @@ mod hash_join_tests { } = result { assert_eq!(results.len(), n, "expected one row per entity"); - let dept_idx = vars.iter().position(|v| v == "?dept").expect("?dept in vars"); + let dept_idx = vars + .iter() + .position(|v| v == "?dept") + .expect("?dept in vars"); let val_idx = vars.iter().position(|v| v == "?v").expect("?v in vars"); // Collect (dept, val) pairs; no entity should appear in both departments. let mut d0_vals: Vec = Vec::new();