From 14d4ff5d179a56a41cfbddea00fe1d8841472eb8 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 24 May 2026 09:09:59 +0530 Subject: [PATCH 1/2] perf(fix): restore per-pattern entity priority in selective_fact_fetch (#282) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit `bb43871` introduced `selective_fact_fetch` but collected all bound entities and all bound attributes across all patterns into two separate sets, then unioned both lookups. For a query like `[:e0 :val ?v]` this caused a broad attribute scan (all `:val` facts) on top of the entity lookup, degrading what should be a µs point-lookup into ms-range scans at scale (2.3–4.9× slower in the concurrent_file/readers_plus_writer benchmark family, confirmed by A/B local Criterion run). Fix: per-pattern selection. A pattern with a bound entity uses the entity index and skips its attribute; a pattern without a bound entity falls back to an attribute lookup if one is available; a pattern with neither causes the whole fetch to fall back to a full scan, which is required for correctness since the fact universe for that pattern cannot be restricted. Regression test added: `test_selective_fetch_prefers_bound_entity_over_attribute_scan` verifies that a bound-entity + bound-attribute pattern fetches only the entity's facts (2), not the entity's facts ∪ all attribute facts (22). Closes #282 Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/executor.rs | 62 +++++++++++++++++++++++++---------- 1 file changed, 45 insertions(+), 17 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 61f9c29a9..a576a8b64 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -369,11 +369,12 @@ impl DatalogExecutor { /// Attempt a selective index-backed fact fetch for the given patterns. /// - /// Inspects `patterns` for bound entity literals (UUID or keyword → deterministic UUID) - /// and bound attribute keywords. If the total distinct lookup count is 0 (nothing bound) - /// or exceeds `threshold` (too many — full scan is cheaper), returns `None`. - /// Otherwise returns `Some(facts)` — the union of all selectively fetched facts, - /// deduplicated by `(entity, attribute, tx_count)`. + /// For each pattern, prefer a bound entity literal (UUID or keyword -> deterministic UUID) + /// over a bound attribute keyword for that same pattern. Entity lookups are usually more + /// selective, but multi-pattern joins still need attribute candidates for patterns that do not + /// bind an entity. If any pattern has neither a bound entity nor a bound attribute, or if the + /// distinct lookup count exceeds `threshold`, returns `None` to use a full scan. Otherwise + /// returns `Some(facts)`, deduplicated by `(entity, attribute, tx_count)`. fn selective_fact_fetch(&self, patterns: &[Pattern], threshold: usize) -> Option> { use std::collections::HashSet; @@ -381,21 +382,21 @@ impl DatalogExecutor { let mut attributes: HashSet = HashSet::new(); for pattern in patterns { - // Bound entity: UUID literal or keyword that resolves deterministically - match &pattern.entity { - EdnValue::Uuid(u) => { - entity_ids.insert(*u); - } - EdnValue::Keyword(_) => { - if let Ok(uid) = edn_to_entity_id(&pattern.entity) { - entity_ids.insert(uid); - } - } - _ => {} + let bound_entity = match &pattern.entity { + EdnValue::Uuid(u) => Some(*u), + EdnValue::Keyword(_) => edn_to_entity_id(&pattern.entity).ok(), + _ => None, + }; + + if let Some(uid) = bound_entity { + entity_ids.insert(uid); + continue; } - // Bound attribute: non-variable keyword + if let AttributeSpec::Real(EdnValue::Keyword(attr)) = &pattern.attribute { attributes.insert(attr.clone()); + } else { + return None; } } @@ -3799,6 +3800,33 @@ mod tests { ); assert_eq!(facts_outside[0].attribute, ":person/name"); } + + #[test] + fn test_selective_fetch_prefers_bound_entity_over_attribute_scan() { + let storage = FactStorage::new(); + let executor = DatalogExecutor::new(storage); + + let mut cmd = String::from(r#"(transact [[:e0 :val 0][:e0 :name "entity0"]"#); + for i in 1..=20 { + cmd.push_str(&format!("[:e{i} :val {i}]")); + } + cmd.push_str("])"); + executor.execute(parse_datalog_command(&cmd).unwrap()).unwrap(); + + let query = match parse_datalog_command("(query [:find ?v :where [:e0 :val ?v]])") + .unwrap() + { + DatalogCommand::Query(query) => query, + _ => panic!("expected query"), + }; + + let facts = executor.filter_facts_for_query(&query).unwrap(); + assert_eq!( + facts.len(), + 2, + "bound entity + attribute query should fetch only the bound entity's facts" + ); + } } #[cfg(test)] From 19bc195a4f0f6a3bdf49f7321872ea448facb101 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 24 May 2026 09:10:14 +0530 Subject: [PATCH 2/2] chore: cargo fmt Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/executor.rs | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index a576a8b64..23ff52492 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -3811,10 +3811,11 @@ mod tests { cmd.push_str(&format!("[:e{i} :val {i}]")); } cmd.push_str("])"); - executor.execute(parse_datalog_command(&cmd).unwrap()).unwrap(); + executor + .execute(parse_datalog_command(&cmd).unwrap()) + .unwrap(); - let query = match parse_datalog_command("(query [:find ?v :where [:e0 :val ?v]])") - .unwrap() + let query = match parse_datalog_command("(query [:find ?v :where [:e0 :val ?v]])").unwrap() { DatalogCommand::Query(query) => query, _ => panic!("expected query"),