diff --git a/benches/helpers/mod.rs b/benches/helpers/mod.rs index a21f610df4..8bac312e53 100644 --- a/benches/helpers/mod.rs +++ b/benches/helpers/mod.rs @@ -331,6 +331,27 @@ pub fn populate_with_dept(n: usize, dept_count: usize) -> Arc { Arc::new(db) } +/// In-memory DB with `n` entities, each with `:val` and `:name` attributes. +/// Suitable for point-lookup and attribute-scan benchmarks. +/// +/// Schema: +/// `:e{i} :val {i}` for i in 0..n +/// `:e{i} :name "entity{i}"` for i in 0..n +pub fn populate_with_names(n: usize) -> Arc { + let db = Minigraf::in_memory().unwrap(); + 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!(r#"[:e{i} :name "entity{i}"]"#, i = i)); + } + cmd.push_str("])"); + db.execute(&cmd).unwrap(); + } + Arc::new(db) +} + /// In-memory DB with `n` value facts, `dup_fraction`% of values are duplicates. /// Each entity has `:val` integer where `dup_fraction`% map to same values. /// diff --git a/benches/minigraf_bench.rs b/benches/minigraf_bench.rs index aaaa840a70..50b86b48bb 100644 --- a/benches/minigraf_bench.rs +++ b/benches/minigraf_bench.rs @@ -1465,6 +1465,44 @@ fn bench_retract(c: &mut Criterion) { } } +// ── B+Tree selective lookup (Issue #208) ───────────────────────────────────── + +fn bench_btree_lookup(c: &mut Criterion) { + const SCALES: &[(&str, usize)] = &[("1k", 1_000), ("10k", 10_000), ("100k", 100_000)]; + + // entity_point: single known entity literal — should be O(1) with selective lookup. + { + let mut group = c.benchmark_group("btree_lookup/entity_point"); + group.sample_size(10); + for &(label, n) in SCALES { + group.bench_with_input(BenchmarkId::from_parameter(label), &n, |b, &n| { + let db = helpers::populate_with_names(n); + b.iter(|| { + db.execute(r#"(query [:find ?n :where [:e0 :name ?n]])"#) + .unwrap() + }); + }); + } + group.finish(); + } + + // attribute_scan: all entities via a single bound attribute. + { + let mut group = c.benchmark_group("btree_lookup/attribute_scan"); + group.sample_size(10); + for &(label, n) in SCALES { + group.bench_with_input(BenchmarkId::from_parameter(label), &n, |b, &n| { + let db = helpers::populate_with_names(n); + b.iter(|| { + db.execute("(query [:find ?e ?n :where [?e :name ?n]])") + .unwrap() + }); + }); + } + group.finish(); + } +} + criterion_group!( benches, bench_insert, @@ -1488,5 +1526,6 @@ criterion_group!( bench_concurrent_btree_scan, bench_prepared, bench_retract, + bench_btree_lookup, ); criterion_main!(benches); diff --git a/docs/superpowers/plans/2026-05-15-issue-208-selective-lookup.md b/docs/superpowers/plans/2026-05-15-issue-208-selective-lookup.md new file mode 100644 index 0000000000..c40dddfde8 --- /dev/null +++ b/docs/superpowers/plans/2026-05-15-issue-208-selective-lookup.md @@ -0,0 +1,670 @@ +# Issue #208 Selective B+Tree Lookup — Implementation Plan + +> **For agentic workers:** REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (`- [ ]`) syntax for tracking. + +**Goal:** Replace the unconditional `get_all_facts()` full scan in `filter_facts_for_query` with index-backed selective fetches when queries bind concrete entity literals or attributes, keeping a guard so we never pay more overhead than a plain full scan. + +**Architecture:** Promote three index-backed methods out of `#[cfg(test)]` in `graph/storage.rs`, add a `selective_fact_fetch` helper on `DatalogExecutor` that inspects main-query patterns for bound entities/attributes and unions their results (up to a threshold of 4 total lookups), then wire it into the `(None, None)` arm of `filter_facts_for_query`. The `as_of` arms and the `facts_override` arm are untouched. + +**Tech Stack:** Rust stable, existing EAVT/AEVT B+tree indexes already maintained in `FactStorage`, `criterion` for benchmarks. + +--- + +## File Map + +| Action | File | What changes | +|--------|------|--------------| +| Modify | `src/graph/storage.rs:618-823` | Split `#[cfg(test)] impl FactStorage` — promote 3 methods to production, leave 5 test-only methods behind | +| Modify | `src/query/datalog/executor.rs` | Add `selective_fact_fetch` method; modify `filter_facts_for_query` | +| Modify | `benches/minigraf_bench.rs` | Add `bench_btree_lookup` function and register it in `criterion_group!` | + +--- + +### Task 1: Promote index methods to production + +**Files:** +- Modify: `src/graph/storage.rs:618-823` + +The current block starting at line 618 is one `#[cfg(test)] impl FactStorage { … }` containing eight methods. We need to split it: three methods become production code, five stay test-only. + +- [ ] **Step 1: Split the impl block** + +In `src/graph/storage.rs`, replace the single `#[cfg(test)] impl FactStorage` block (lines 618–823) with two blocks. The first block is new production code (no `#[cfg(test)]`), the second retains the remaining test-only methods. + +The new production block goes right before the `#[cfg(test)] impl FactStorage` block: + +```rust +/// Index-backed selective fetches. Available in production for the query executor. +impl FactStorage { + /// Get all facts for a specific entity using the EAVT B+tree index. + /// + /// Falls back to a linear scan when no index is available (e.g. before the first + /// checkpoint on a fresh in-memory DB). + pub(crate) fn get_facts_by_entity(&self, entity_id: &EntityId) -> Result> { + use crate::storage::index::EavtKey; + let d = self.data.read().unwrap(); + + let start = EavtKey { + entity: *entity_id, + attribute: String::new(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + }; + let next_entity = uuid::Uuid::from_u128(entity_id.as_u128().wrapping_add(1)); + let end = EavtKey { + entity: next_entity, + attribute: String::new(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + }; + + // Fallback: no indexes built yet + if d.pending_indexes.eavt.is_empty() && d.committed_index_reader.is_none() { + if d.committed.is_none() { + return Ok(d + .facts + .iter() + .filter(|f| &f.entity == entity_id) + .cloned() + .collect()); + } + let mut result: Vec = d + .facts + .iter() + .filter(|f| &f.entity == entity_id) + .cloned() + .collect(); + if let Some(loader) = &d.committed { + for fact in loader.stream_all()? { + if &fact.entity == entity_id { + result.push(fact); + } + } + } + return Ok(result); + } + + let mut facts = Vec::new(); + + // Pending: in-memory BTreeMap bounded range. + for (key, &fr) in d.pending_indexes.eavt.range(start.clone()..end.clone()) { + if key.entity != *entity_id { + break; + } + facts.push(resolve_fact_ref(&d, fr)?); + } + + // Committed: on-disk B+tree range scan + if let Some(reader) = &d.committed_index_reader { + let committed_refs = reader.range_scan_eavt(&start, Some(&end))?; + for fr in committed_refs { + facts.push(resolve_fact_ref(&d, fr)?); + } + } + + Ok(facts) + } + + /// Get all facts for a specific attribute using the AEVT B+tree index. + pub(crate) fn get_facts_by_attribute(&self, attribute: &Attribute) -> Result> { + use crate::storage::index::AevtKey; + let d = self.data.read().unwrap(); + + // Fallback: no index + if d.pending_indexes.aevt.is_empty() && d.committed_index_reader.is_none() { + drop(d); + return Ok(self + .get_all_facts()? + .into_iter() + .filter(|f| &f.attribute == attribute) + .collect()); + } + + let start = AevtKey { + attribute: attribute.clone(), + entity: uuid::Uuid::nil(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + }; + let end_opt: Option = next_string_prefix(attribute).map(|next_attr| AevtKey { + attribute: next_attr, + entity: uuid::Uuid::nil(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + }); + + let mut facts = Vec::new(); + + // Pending + let pending_range: Vec = match &end_opt { + Some(end) => d + .pending_indexes + .aevt + .range(start.clone()..end.clone()) + .filter(|(k, _)| k.attribute == *attribute) + .map(|(_, &r)| r) + .collect(), + None => d + .pending_indexes + .aevt + .range(start.clone()..) + .take_while(|(k, _)| k.attribute == *attribute) + .map(|(_, &r)| r) + .collect(), + }; + for fr in pending_range { + facts.push(resolve_fact_ref(&d, fr)?); + } + + // Committed + if let Some(reader) = &d.committed_index_reader { + let committed_refs = reader.range_scan_aevt(&start, end_opt.as_ref())?; + for fr in committed_refs { + let fact = resolve_fact_ref(&d, fr)?; + if &fact.attribute == attribute { + facts.push(fact); + } + } + } + + Ok(facts) + } + + /// Get all facts for a specific entity and attribute. + pub(crate) fn get_facts_by_entity_attribute( + &self, + entity_id: &EntityId, + attribute: &Attribute, + ) -> Result> { + let all = self.get_all_facts()?; + Ok(all + .into_iter() + .filter(|f| &f.entity == entity_id && &f.attribute == attribute) + .collect()) + } +} +``` + +Then update the `#[cfg(test)] impl FactStorage` block comment and remove the three promoted methods from it, leaving only: + +```rust +/// Test-only helpers: for use in tests, not the production query path. +#[cfg(test)] +impl FactStorage { + /// Return all asserted facts valid at the given timestamp. Test use only. + pub(crate) fn get_facts_valid_at(&self, ts: i64) -> Result> { … } + + /// Get the current value for an entity-attribute pair. Test use only. + pub(crate) fn get_current_value(…) -> Result> { … } + + /// Get the count of all facts in storage. Test use only. + pub(crate) fn fact_count(&self) -> usize { … } + + /// Get the count of currently asserted facts. Test use only. + pub(crate) fn asserted_fact_count(&self) -> usize { … } + + /// Returns (eavt_len, aevt_len, avet_len, vaet_len). Test use only. + pub(crate) fn index_counts(&self) -> (usize, usize, usize, usize) { … } +} +``` + +(Keep the full bodies of all five methods unchanged — only move them into the new smaller `#[cfg(test)]` block.) + +- [ ] **Step 2: Verify it compiles** + +```bash +cargo build 2>&1 | head -20 +``` + +Expected: no errors. If `resolve_fact_ref` or `next_string_prefix` are not in scope in the new block, check that they are defined as free functions in the same file (they are — search for `fn resolve_fact_ref` and `fn next_string_prefix` to confirm line numbers). + +- [ ] **Step 3: Run existing storage tests** + +```bash +cargo test --test '*' 2>&1 | grep -E "FAILED|error\[" | head -20 +cargo test graph::storage 2>&1 | tail -5 +``` + +Expected: all pass. The promoted methods were already tested; we haven't changed any logic. + +- [ ] **Step 4: Commit** + +```bash +git add src/graph/storage.rs +git commit -m "refactor: promote get_facts_by_entity/attribute to production code (#208)" +``` + +--- + +### Task 2: Write failing tests for selective lookup behaviour + +**Files:** +- Modify: `src/query/datalog/executor.rs` (add test module entries) + +These tests verify that entity-bound and attribute-bound queries return the right results after the optimisation is applied. They test behaviour, not internals — no spying on which method was called. + +- [ ] **Step 1: Write the tests** + +Locate the `#[cfg(test)]` module near the bottom of `src/query/datalog/executor.rs`. Add these tests: + +```rust +#[cfg(test)] +mod selective_lookup_tests { + use crate::graph::FactStorage; + use crate::query::datalog::executor::DatalogExecutor; + + + fn make_db_with_entities(n: 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!(r#"[:e{i} :name "entity{i}"]"#, i = i)); + 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 + } + + #[test] + fn entity_bound_query_returns_correct_results() { + let exec = make_db_with_entities(100); + // Point lookup: only entity :e5 + let result = exec + .execute(crate::query::datalog::parser::parse_datalog_command(r#"(query [:find ?n :where [:e5 :name ?n]])"#).unwrap()) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { + assert_eq!(results.len(), 1, "expected exactly 1 result for entity :e5"); + assert_eq!( + results[0][0], + crate::graph::types::Value::String("entity5".to_string()) + ); + } else { + panic!("expected QueryResults"); + } + } + + #[test] + fn attribute_bound_query_returns_correct_results() { + let exec = make_db_with_entities(100); + // All entities with :val + let result = exec + .execute(crate::query::datalog::parser::parse_datalog_command("(query [:find ?e ?v :where [?e :val ?v]])").unwrap()) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { + assert_eq!(results.len(), 100, "expected 100 results for :val attribute scan"); + } else { + panic!("expected QueryResults"); + } + } + + #[test] + fn query_with_many_bound_entities_returns_correct_results() { + // 6 entity literals → exceeds threshold of 4 → falls back to full scan + // Result must still be correct + let exec = make_db_with_entities(100); + let result = exec + .execute(crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?n :where [?e :name ?n] \ + (or [:e0 :val ?v0] [:e1 :val ?v1] [:e2 :val ?v2] \ + [:e3 :val ?v3] [:e4 :val ?v4] [:e5 :val ?v5])])", + ).unwrap()) + .unwrap(); + // We just need it to not panic and return a non-empty result + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { + assert!(!results.is_empty(), "expected non-empty results"); + } else { + panic!("expected QueryResults"); + } + } + + #[test] + fn as_of_query_still_works_after_change() { + let exec = make_db_with_entities(10); + // as_of query must work — it takes the full-scan path regardless + let result = exec + .execute(crate::query::datalog::parser::parse_datalog_command("(query [:find ?n :where [?e :name ?n] :as-of 1])").unwrap()) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { + // as-of 1 (first tx) should return the first batch + assert!(!results.is_empty(), "expected results from as-of 1 query"); + } else { + panic!("expected QueryResults"); + } + } +} +``` + +- [ ] **Step 2: Run the tests to verify they compile and pass (they should pass even before the optimisation, since correctness is what we're testing)** + +```bash +cargo test selective_lookup_tests 2>&1 | tail -10 +``` + +Expected: all 4 tests pass. These tests verify existing behaviour — confirming the baseline before we touch executor.rs. + +- [ ] **Step 3: Commit** + +```bash +git add src/query/datalog/executor.rs +git commit -m "test: add selective lookup correctness tests (#208)" +``` + +--- + +### Task 3: Implement `selective_fact_fetch` + +**Files:** +- Modify: `src/query/datalog/executor.rs` — add method on `DatalogExecutor` + +- [ ] **Step 1: Add `selective_fact_fetch` as a private method on `DatalogExecutor`** + +Find the `impl DatalogExecutor` block (starts around line 96). Add this method after `filter_facts_for_query` (after line ~338): + +```rust +/// Attempt a selective index-backed fact fetch for the given patterns. +/// +/// Inspects `patterns` for bound entity literals (UUID or keyword → UUID) and bound +/// attribute strings. If the total distinct lookup count is 0 (no bound values) 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)`. +fn selective_fact_fetch( + &self, + patterns: &[Pattern], + threshold: usize, +) -> Option> { + use crate::query::datalog::matcher::edn_to_entity_id; + use std::collections::HashSet; + + let mut entity_ids: HashSet = HashSet::new(); + let mut attributes: HashSet = HashSet::new(); + + for pattern in patterns { + // Bound entity literal (UUID 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); + } + } + _ => {} + } + // Bound attribute (non-variable Real attribute) + if let AttributeSpec::Real(EdnValue::Keyword(attr)) = &pattern.attribute { + attributes.insert(attr.clone()); + } + } + + let total = entity_ids.len() + attributes.len(); + if total == 0 || total > threshold { + return None; + } + + // Dedup key: (entity uuid, attribute string, tx_count) — no Value formatting needed. + let mut seen: HashSet<(uuid::Uuid, String, u64)> = HashSet::new(); + let mut all_facts: Vec = Vec::new(); + + for uid in &entity_ids { + match self.storage.get_facts_by_entity(uid) { + Ok(facts) => { + for fact in facts { + let key = (fact.entity, fact.attribute.clone(), fact.tx_count); + if seen.insert(key) { + all_facts.push(fact); + } + } + } + Err(_) => return None, // storage error → fall back to full scan + } + } + + for attr in &attributes { + match self.storage.get_facts_by_attribute(attr) { + Ok(facts) => { + for fact in facts { + let key = (fact.entity, fact.attribute.clone(), fact.tx_count); + if seen.insert(key) { + all_facts.push(fact); + } + } + } + Err(_) => return None, + } + } + + Some(all_facts) +} +``` + +- [ ] **Step 2: Wire it into `filter_facts_for_query`** + +Find the `(None, None)` arm of the `match` statement in `filter_facts_for_query` (around line 308): + +```rust +// BEFORE: +(None, None) => self.storage.get_all_facts()?, +``` + +Replace with: + +```rust +// AFTER: +(None, None) => { + let patterns = query.get_patterns(); + self.selective_fact_fetch(&patterns, 4) + .unwrap_or_else(|| self.storage.get_all_facts().unwrap_or_default()) +} +``` + +Wait — the surrounding `match` arm is inside a `Result` context. Look at the exact shape: + +```rust +let source_facts: Vec = match (&self.facts_override, query.as_of.as_ref()) { + (Some(facts), Some(as_of)) => { … } + (Some(facts), None) => facts.iter().cloned().collect(), + (None, Some(as_of)) => self.storage.get_facts_as_of(as_of)?, + (None, None) => self.storage.get_all_facts()?, +}; +``` + +Replace only the last arm: + +```rust + (None, None) => { + let patterns = query.get_patterns(); + match self.selective_fact_fetch(&patterns, 4) { + Some(facts) => facts, + None => self.storage.get_all_facts()?, + } + } +``` + +- [ ] **Step 3: Verify it compiles** + +```bash +cargo build 2>&1 | head -20 +``` + +Expected: no errors. + +- [ ] **Step 4: Run the tests from Task 2** + +```bash +cargo test selective_lookup_tests 2>&1 | tail -10 +``` + +Expected: all 4 pass. + +- [ ] **Step 5: Run the full test suite** + +```bash +cargo test 2>&1 | tail -15 +``` + +Expected: all 795+ tests pass. Zero failures. + +- [ ] **Step 6: Commit** + +```bash +git add src/query/datalog/executor.rs +git commit -m "feat: selective B+Tree lookup in filter_facts_for_query (#208)" +``` + +--- + +### Task 4: Add benchmarks + +**Files:** +- Modify: `benches/minigraf_bench.rs` — add `bench_btree_lookup` function +- Modify: `benches/helpers/mod.rs` — add `populate_with_point_lookups` helper + +- [ ] **Step 1: Add a helper to `benches/helpers/mod.rs`** + +After `populate_with_dept`, add: + +```rust +/// In-memory DB with `n` entities, each with `:val` and `:name` attributes. +/// Suitable for point-lookup and attribute-scan benchmarks. +/// +/// Schema: +/// `:e{i} :val {i}` for i in 0..n +/// `:e{i} :name "entity{i}"` for i in 0..n +pub fn populate_with_names(n: usize) -> Arc { + let db = Minigraf::in_memory().unwrap(); + 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!(r#"[:e{i} :name "entity{i}"]"#, i = i)); + } + cmd.push_str("])"); + db.execute(&cmd).unwrap(); + } + Arc::new(db) +} +``` + +- [ ] **Step 2: Add `bench_btree_lookup` to `benches/minigraf_bench.rs`** + +Add this function before the `criterion_group!` macro at the bottom: + +```rust +// ── B+Tree selective lookup (Issue #208) ───────────────────────────────────── +// Baseline benchmarks for point-entity and attribute-scan queries. +// Used to measure the effect of selective vs full-scan fetch. + +fn bench_btree_lookup(c: &mut Criterion) { + const SCALES: &[(&str, usize)] = &[("1k", 1_000), ("10k", 10_000), ("100k", 100_000)]; + + // entity_point: query a single known entity literal. + // Should be O(1) in entity count with selective lookup. + { + let mut group = c.benchmark_group("btree_lookup/entity_point"); + group.sample_size(10); + for &(label, n) in SCALES { + group.bench_with_input(BenchmarkId::from_parameter(label), &n, |b, &n| { + let db = helpers::populate_with_names(n); + b.iter(|| { + db.execute(r#"(query [:find ?n :where [:e0 :name ?n]])"#) + .unwrap() + }); + }); + } + group.finish(); + } + + // attribute_scan: scan all entities via a single bound attribute. + // Should be O(matching facts) rather than O(all facts) with selective lookup. + { + let mut group = c.benchmark_group("btree_lookup/attribute_scan"); + group.sample_size(10); + for &(label, n) in SCALES { + group.bench_with_input(BenchmarkId::from_parameter(label), &n, |b, &n| { + let db = helpers::populate_with_names(n); + b.iter(|| { + db.execute("(query [:find ?e ?n :where [?e :name ?n]])") + .unwrap() + }); + }); + } + group.finish(); + } +} +``` + +- [ ] **Step 3: Register the new benchmark group** + +In the `criterion_group!` macro at the bottom of `benches/minigraf_bench.rs`, add `bench_btree_lookup` to the list: + +```rust +criterion_group!( + benches, + bench_insert, + bench_insert_file, + bench_query, + bench_time_travel, + bench_recursion, + bench_negation, + bench_disjunction, + bench_aggregation, + bench_expr, + bench_window, + bench_temporal_metadata, + bench_udf, + bench_aggregation_extras, + bench_query_extras, + bench_open, + bench_checkpoint, + bench_concurrent, + bench_concurrent_file, + bench_concurrent_btree_scan, + bench_prepared, + bench_retract, + bench_btree_lookup, // ← new +); +criterion_main!(benches); +``` + +- [ ] **Step 4: Verify benchmarks compile** + +```bash +cargo bench --no-run 2>&1 | tail -5 +``` + +Expected: `Compiling minigraf …` then `Finished`. No errors. + +- [ ] **Step 5: Run just the new benchmarks (quick smoke check)** + +```bash +cargo bench btree_lookup -- --sample-size 3 2>&1 | tail -20 +``` + +Expected: two groups run, numbers printed, no panics. + +- [ ] **Step 6: Run full test suite one last time** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all tests pass. + +- [ ] **Step 7: Commit** + +```bash +git add benches/minigraf_bench.rs benches/helpers/mod.rs +git commit -m "bench: add btree_lookup/entity_point and attribute_scan benchmarks (#208)" +``` diff --git a/docs/superpowers/plans/2026-05-15-issues-202-203-204-hash-join.md b/docs/superpowers/plans/2026-05-15-issues-202-203-204-hash-join.md new file mode 100644 index 0000000000..a211d4dc0c --- /dev/null +++ b/docs/superpowers/plans/2026-05-15-issues-202-203-204-hash-join.md @@ -0,0 +1,1129 @@ +# Issues #202 + #203 + #204 Hash-Join Cluster — Implementation Plan + +> **For agentic workers:** REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (`- [ ]`) syntax for tracking. + +**Goal:** Eliminate three O(N²) inner loops in the query engine — negation pre-filters (#202), disjunction branch evaluation (#203), and the general pattern join (#204) — by replacing nested fact scans with hash-based lookups. + +**Architecture:** Three surgical fixes, one per site: +- **#202** (`executor.rs` + `evaluator.rs`): pre-compute not/not-join exclusion sets once, probe per outer binding. +- **#203** (`executor.rs`): evaluate or/or-join branches from an empty seed, hash-join results back onto incoming bindings. +- **#204** (`matcher.rs`): detect shared join variables between patterns and build a hash map from candidate facts, replacing the nested-loop scan in `join_with_pattern`. + +Each fix is independent; implement in order (#202 → #203 → #204) since they touch different functions. + +**Tech Stack:** Rust stable, `std::collections::HashMap` / `HashSet`, existing `PatternMatcher` and `evaluate_not_join` APIs. + +--- + +## File Map + +| Action | File | What changes | +|--------|------|--------------| +| Modify | `src/query/datalog/executor.rs:438-470` | #202 not-filter: pre-compute exclusion set before filter loop | +| Modify | `src/query/datalog/evaluator.rs:477-529` | #202 evaluate_not_join: pre-compute before outer binding loop | +| Modify | `src/query/datalog/executor.rs:1370-1448` | #203 apply_or_clauses: empty-seed branch eval + hash-join back | +| Modify | `src/query/datalog/matcher.rs:396-410` | #204 join_with_pattern: hash-join when shared variable detected | + +--- + +### Task 1: #202 — Pre-compute not/not-join exclusion sets in `execute_query` + +**Files:** +- Modify: `src/query/datalog/executor.rs:438-470` + +**Background:** The current code at lines 438–470 calls `not_body_matches(not_body, binding, …)` for each outer `binding`. `not_body_matches` creates a fresh `PatternMatcher` and scans all facts every call → O(outer × inner). + +The fix: before the filter loop, evaluate each not-body patterns once against `filtered_facts`, collect the set of "excluded" join-variable tuples, then check the set per binding. + +- [ ] **Step 1: Write a failing test that would distinguish O(N) from O(N²)** + +Add to the `#[cfg(test)]` module in `src/query/datalog/executor.rs`: + +```rust +#[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"); + } + } +} +``` + +- [ ] **Step 2: Run the tests (expect pass — correctness baseline)** + +```bash +cargo test not_hash_join_tests 2>&1 | tail -8 +``` + +Expected: both tests pass. + +- [ ] **Step 3: Replace the not-filter loop with pre-computed exclusion sets** + +In `execute_query` (around lines 438–470), the current code is: + +```rust +let not_filtered: Vec<_> = if not_clauses.is_empty() && not_join_clauses.is_empty() { + bindings +} else { + 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; + } + } + for (join_vars, nj_clauses) in ¬_join_clauses { + if evaluate_not_join( + join_vars, + nj_clauses, + binding, + filtered_facts.clone(), + ®istry, + ) { + return false; + } + } + true + }) + .collect() +}; +``` + +Replace with: + +```rust +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 crate::query::datalog::evaluator::substitute_pattern; + 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 = crate::query::datalog::matcher::PatternMatcher::from_slice_with_valid_at( + filtered_facts.clone(), + valid_at_value.clone(), + ); + let body_bindings = matcher.match_patterns(&patterns); + // Determine which variable names are join variables: those that appear in + // the not-body patterns AND in the incoming bindings. We discover these + // dynamically from the body binding keys. + // We 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 --- + let not_join_exclusion_sets: Vec>>> = + 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 = + crate::query::datalog::matcher::PatternMatcher::from_slice_with_valid_at( + filtered_facts.clone(), + valid_at_value.clone(), + ); + let body_bindings = matcher.match_patterns(&patterns); + // Project to join_vars only. + let exclusion_set: HashSet> = body_bindings + .into_iter() + .filter_map(|b| { + let kv: Vec<(String, Value)> = join_vars + .iter() + .filter_map(|v| b.get(v).map(|val| (v.clone(), val.clone()))) + .collect(); + if kv.len() == join_vars.len() { + Some(kv) + } else { + None + } + }) + .collect(); + Some(exclusion_set) + }) + .collect(); + + bindings + .into_iter() + .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) => { + // Build this binding's key (variables present in the exclusion set). + // Project binding to the variables in the not-body patterns. + let has_expr = not_body.iter().any(|c| matches!(c, WhereClause::Expr { .. })); + let patterns: Vec<_> = not_body + .iter() + .filter_map(|c| match c { + WhereClause::Pattern(p) => Some(substitute_pattern(p, binding)), + _ => None, + }) + .collect(); + // Collect the variable names from the pattern (post-substitution + // variables that are still unbound — shouldn't be any for bound + // outer bindings, but we handle the general case). + // Simple approach: intersect binding with the not-body pattern vars, + // form a sorted key, and probe the set. + // Get the variable names directly from the exclusion_set entries. + if exclusion_set.is_empty() { + // No excluding bindings → this outer binding is safe. + // But only if there are no expr clauses making it complex. + if !has_expr { + continue; + } + // Fall through to slow path if there are expr clauses. + } + if !has_expr && !patterns.is_empty() { + // Fast path: probe exclusion set using the outer binding's + // values for the join variables. + // Determine join variable names from a sample set entry. + 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; + } + } + } + } + + // Check not-join-bodies. + for (i, (join_vars, nj_clauses)) in not_join_clauses.iter().enumerate() { + match ¬_join_exclusion_sets[i] { + Some(exclusion_set) => { + let has_expr = nj_clauses + .iter() + .any(|c| matches!(c, WhereClause::Expr { .. })); + if !has_expr { + let key: Vec<(String, Value)> = join_vars + .iter() + .filter_map(|v| { + binding.get(v).map(|val| (v.clone(), val.clone())) + }) + .collect(); + if key.len() == join_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 + }) + .collect() +}; +``` + +- [ ] **Step 4: Build** + +```bash +cargo build 2>&1 | head -20 +``` + +Expected: no errors. Fix any `use` import issues (add `use crate::query::datalog::evaluator::substitute_pattern;` at the top of the function if needed — it's already imported at line 821 inside `not_body_matches`, but you may need it earlier in the file). + +- [ ] **Step 5: Run not-hash-join tests** + +```bash +cargo test not_hash_join_tests 2>&1 | tail -8 +``` + +Expected: both tests pass. + +- [ ] **Step 6: Run full test suite** + +```bash +cargo test 2>&1 | tail -10 +``` + +Expected: all tests pass. + +- [ ] **Step 7: Commit** + +```bash +git add src/query/datalog/executor.rs +git commit -m "perf: pre-compute not/not-join exclusion sets — O(N²) → O(N) (#202)" +``` + +--- + +### Task 2: #203 — Empty-seed branch evaluation in `apply_or_clauses` + +**Files:** +- Modify: `src/query/datalog/executor.rs:1370-1448` + +**Background:** `apply_or_clauses` calls `evaluate_branch(branch, bindings.clone(), …)` for each branch. `evaluate_branch` uses `match_patterns_seeded` which iterates every incoming binding × every fact → O(seeds × facts). The fix: evaluate branches from an empty seed, then hash-join results back onto incoming bindings. + +- [ ] **Step 1: Write failing tests** + +Add to the `#[cfg(test)]` module in `executor.rs`: + +```rust +#[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"); + } + } +} +``` + +- [ ] **Step 2: Run tests (expect pass — correctness baseline)** + +```bash +cargo test or_hash_join_tests 2>&1 | tail -8 +``` + +Expected: all 3 pass. + +- [ ] **Step 3: Replace `apply_or_clauses` body** + +Find `apply_or_clauses` at around line 1370. Replace the entire function body (keep the signature unchanged): + +```rust +pub(crate) fn apply_or_clauses( + clauses: &[WhereClause], + mut bindings: Vec, + storage: Arc<[Fact]>, + rules: &crate::query::datalog::rules::RuleRegistry, + as_of: Option, + valid_at: Option, + registry: &FunctionRegistry, +) -> anyhow::Result> { + for clause in clauses { + match clause { + WhereClause::Or(branches) => { + // 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(); + + for branch in branches { + let branch_result = evaluate_branch( + branch, + empty_seed.clone(), + storage.clone(), + rules, + as_of.clone(), + valid_at.clone(), + registry, + )?; + for b in branch_result { + 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_keys.insert(key) { + union_bindings.push(b); + } + } + } + + // Determine shared variable names: variables present in both + // incoming bindings and branch results. + let branch_var_names: std::collections::HashSet<&str> = union_bindings + .iter() + .flat_map(|b| b.keys().map(|k| k.as_str())) + .collect(); + let shared_vars: Vec = bindings + .iter() + .flat_map(|b| b.keys().cloned()) + .collect::>() + .into_iter() + .filter(|v| 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, + } => { + let outer_keys: std::collections::HashSet = + bindings.iter().flat_map(|b| b.keys().cloned()).collect(); + + let empty_seed: Vec = vec![HashMap::new()]; + let mut projected: Vec = Vec::new(); + let mut seen_proj: std::collections::HashSet> = + std::collections::HashSet::new(); + + for branch in branches { + let branch_result = evaluate_branch( + branch, + empty_seed.clone(), + storage.clone(), + rules, + as_of.clone(), + valid_at.clone(), + registry, + )?; + for mut b in branch_result { + if !join_vars.iter().all(|v| b.contains_key(v)) { + continue; + } + // Project to outer_keys (preserves join_vars since join_vars ⊆ outer_keys) + b.retain(|k, _| outer_keys.contains(k)); + 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; + } + + _ => {} + } + } + Ok(bindings) +} +``` + +- [ ] **Step 4: Build** + +```bash +cargo build 2>&1 | head -20 +``` + +Expected: no errors. + +- [ ] **Step 5: Run or-hash-join tests** + +```bash +cargo test or_hash_join_tests 2>&1 | tail -8 +``` + +Expected: all 3 pass. + +- [ ] **Step 6: Run full test suite** + +```bash +cargo test 2>&1 | tail -10 +``` + +Expected: all tests pass. + +- [ ] **Step 7: Commit** + +```bash +git add src/query/datalog/executor.rs +git commit -m "perf: empty-seed branch eval in apply_or_clauses — O(N²) → O(N) (#203)" +``` + +--- + +### Task 3: #204 — Hash-join in `join_with_pattern` + +**Files:** +- Modify: `src/query/datalog/matcher.rs:396-410` + +**Background:** `join_with_pattern` calls `match_pattern_with_bindings(pattern, existing)` for every `existing` binding — for each call, `match_pattern_with_bindings_scan` iterates all facts. This is O(existing × facts). When the pattern shares a variable (e.g. `?e`) with existing bindings, we can build a HashMap> from the facts once, then probe per existing binding. + +- [ ] **Step 1: Write failing tests** + +Add to the `#[cfg(test)]` module in `src/query/datalog/matcher.rs`: + +```rust +#[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 + } + + #[test] + fn two_pattern_join_returns_correct_count() { + let n = 1_000; + let exec = make_join_db(n, 10); + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?dept (sum ?v) :with ?e \ + :where [?e :dept ?dept] [?e :val ?v]])", + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result + { + // 10 departments → 10 result rows + assert_eq!(results.len(), 10, "expected 10 department groups"); + } else { + panic!("expected QueryResults"); + } + } + + #[test] + fn two_pattern_join_values_are_correct() { + // 10 entities, 2 depts. Dept :d0 gets e0,e2,e4,e6,e8 (vals 0,2,4,6,8 → sum=20) + // Dept :d1 gets e1,e3,e5,e7,e9 (vals 1,3,5,7,9 → sum=25) + let n = 10; + let exec = make_join_db(n, 2); + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?dept (sum ?v) :with ?e \ + :where [?e :dept ?dept] [?e :val ?v]])", + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { + vars, results, .. + } = result + { + assert_eq!(results.len(), 2, "expected 2 department groups"); + // Find the sum for :d0 + let dept_idx = vars.iter().position(|v| v == "?dept").unwrap_or(0); + let sum_idx = 1 - dept_idx; // the other column + let mut sums: std::collections::HashMap = std::collections::HashMap::new(); + for row in &results { + if let ( + crate::graph::types::Value::Keyword(dept), + crate::graph::types::Value::Integer(sum), + ) = (&row[dept_idx], &row[sum_idx]) + { + sums.insert(dept.clone(), *sum); + } + } + assert_eq!(sums.get(":d0"), Some(&20), "sum for :d0 should be 20"); + assert_eq!(sums.get(":d1"), Some(&25), "sum for :d1 should be 25"); + } else { + panic!("expected QueryResults"); + } + } +} +``` + +- [ ] **Step 2: Run tests (expect pass — baseline)** + +```bash +cargo test hash_join_tests 2>&1 | tail -8 +``` + +Expected: both pass. + +- [ ] **Step 3: Replace `join_with_pattern` with hash-join implementation** + +Find `join_with_pattern` at around line 396. Replace it (keep `match_pattern_with_bindings` and all other methods unchanged): + +```rust +/// 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 { + if existing_bindings.is_empty() { + return vec![]; + } + + // 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()); + // Note: match_pattern uses an empty binding — it produces all possible bindings. + + // 2. Build HashMap: join_var_value → Vec + let mut build_side: HashMap> = HashMap::new(); + for b in candidate_bindings { + if let Some(val) = b.get(&jvar) { + build_side.entry(val.clone()).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; + }; + if let Some(matches) = build_side.get(probe_val) { + for candidate in matches { + // Merge and consistency-check (reuse existing logic via a combined binding). + 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) { + if existing_val != 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 +} +``` + +- [ ] **Step 4: Build** + +```bash +cargo build 2>&1 | head -20 +``` + +Expected: no errors. Note: `match_pattern` is already a public method on `PatternMatcher` (line 71 of matcher.rs). + +- [ ] **Step 5: Run hash-join tests** + +```bash +cargo test hash_join_tests 2>&1 | tail -8 +``` + +Expected: both tests pass. + +- [ ] **Step 6: Run full test suite** + +```bash +cargo test 2>&1 | tail -10 +``` + +Expected: all tests pass. This is the most impactful change — if any join test fails, check that the consistency-check logic handles all `Value` variants and hidden `__f` keys correctly (compare with the original `match_pattern_with_bindings_scan`). + +- [ ] **Step 7: Commit** + +```bash +git add src/query/datalog/matcher.rs +git commit -m "perf: hash-join in join_with_pattern — O(N²) → O(N) (#204)" +``` + +--- + +### Task 4: Final verification and benchmark smoke-check + +**Files:** None changed. + +- [ ] **Step 1: Run full test suite** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all tests pass. + +- [ ] **Step 2: Smoke-check the relevant benchmarks (quick, not a full run)** + +```bash +cargo bench negation -- --sample-size 3 2>&1 | grep "not_scale" +cargo bench disjunction -- --sample-size 3 2>&1 | grep "or_scale" +cargo bench aggregation -- --sample-size 3 2>&1 | grep "with_grouped_sum" +``` + +Expected: all three groups complete without panics. Numbers will vary; what matters is they finish without errors. + +- [ ] **Step 3: Verify no `{:?}` debug-format of sensitive types in new test code** + +```bash +grep -n '{:?}' src/query/datalog/executor.rs src/query/datalog/matcher.rs src/query/datalog/evaluator.rs | grep -v "//.*{:?}" | head -20 +``` + +Expected: any matches should be in existing code, not in the tests added in this plan. New test assertions in this plan use `.len()`, direct `Value` comparisons, and `.is_empty()` — not `{:?}` on Result/Fact/Value. + +- [ ] **Step 4: Final commit summary** + +```bash +git log --oneline -6 +``` + +Expected output (roughly): +``` + perf: hash-join in join_with_pattern — O(N²) → O(N) (#204) + perf: empty-seed branch eval in apply_or_clauses — O(N²) → O(N) (#203) + perf: pre-compute not/not-join exclusion sets — O(N²) → O(N) (#202) + test: add selective lookup correctness tests (#208) ← from Plan 1 PR +… +``` diff --git a/docs/superpowers/specs/2026-05-15-wave1-performance-design.md b/docs/superpowers/specs/2026-05-15-wave1-performance-design.md new file mode 100644 index 0000000000..c352cf27d7 --- /dev/null +++ b/docs/superpowers/specs/2026-05-15-wave1-performance-design.md @@ -0,0 +1,202 @@ +# Wave 1 Performance Design: O(N²) → O(N) + +**Date**: 2026-05-15 +**Issues**: #208, #202, #203, #204 +**Delivery**: 2 PRs + +--- + +## Overview + +Wave 1 addresses four O(N²) performance bottlenecks in the query engine. All four are +pure algorithmic fixes — no API changes, no file-format changes, no new dependencies. + +**PR 1** — #208: B+Tree selective lookup (prerequisite for #229 SIMD benchmarking) +**PR 2** — #202 + #203 + #204: Hash-join cluster (negation, disjunction, general join) + +--- + +## PR 1 — #208: Selective B+Tree Lookup + +### Problem + +`filter_facts_for_query` (executor.rs:300) always calls `get_all_facts()`, which reads +every committed page from disk plus all pending in-memory facts — a full sequential scan +regardless of how selective the query patterns are. + +`get_facts_by_entity` and `get_facts_by_attribute` already exist in `graph/storage.rs` +with correct EAVT/AEVT B+tree index logic (committed + pending layers), but are gated +`#[cfg(test)]` only. + +### Storage layer changes (`src/graph/storage.rs`) + +Remove `#[cfg(test)]` from: +- `get_facts_by_entity` +- `get_facts_by_attribute` +- `get_facts_by_entity_attribute` + +No logic changes to these methods. + +### Executor changes (`src/query/datalog/executor.rs`) + +Add private helper: + +``` +fn selective_fact_fetch( + storage: &FactStorage, + patterns: &[Pattern], + threshold: usize, // suggested: 4 +) -> Option> +``` + +Logic: +1. Walk main-query patterns (not not/not-join bodies). +2. Collect distinct bound entity literals (`EdnValue::Uuid`) and bound attribute strings + (non-variable `AttributeSpec::Real`). +3. Count total lookups = `distinct_entities + distinct_attributes`. +4. If count == 0 or count > threshold: return `None` → caller falls back to `get_all_facts()`. +5. Otherwise: call `get_facts_by_entity` per entity + `get_facts_by_attribute` per + attribute, union into one `Vec`, deduplicate by `(entity, attribute, value, + tx_count)` key. + +Modify `filter_facts_for_query`: +- In the `(None, None)` arm (no `facts_override`, no `as_of`): call + `selective_fact_fetch` first; use its result if `Some`, fall back to `get_all_facts()` + otherwise. +- The `as_of` arms always use `get_facts_as_of` (time-travel queries require the full + log for correctness). +- Steps 2 and 3 (net-assert, valid-time filter) are unchanged. + +### Guard rationale + +Threshold of 4: at 5+ distinct index lookups, the sum of B+tree traversal overhead +(page cache lookups, per-entry allocation) can exceed a single sequential page scan, +especially on a warm page cache. `not`/`not-join` bodies are excluded from the count +because their attributes are often high-cardinality; they receive the same `Arc<[Fact]>` +and are already correct with the reduced set (not bodies constrain variables already +bound by main patterns). + +### Tests + +- Entity-bound point query uses selective path (verify via correct result count against + known population, not via spy — avoids coupling tests to internals). +- Attribute-bound query (e.g. `[?e :person/name ?n]`) uses selective path. +- Query with 5+ distinct entity/attribute lookups falls back to full scan (result correct). +- `as_of` queries always take full-scan path (result correct). +- Full existing test suite passes with no regressions. + +### Benchmarks + +Add new benchmark groups (at 1k/10k/100k scale): +- `btree_lookup/entity_point` — single entity literal, all attributes +- `btree_lookup/attribute_scan` — single bound attribute, all entities + +These establish the performance baseline that #229 (SIMD) will build on. + +--- + +## PR 2 — #202 + #203 + #204: Hash-Join Cluster + +### #202 — Pre-computed not/not-join exclusion sets + +**File**: `src/query/datalog/executor.rs` (execute_query not-filter section) +**File**: `src/query/datalog/evaluator.rs` (evaluate_not_join) + +**Problem**: `not_body_matches` and `evaluate_not_join` create a fresh `PatternMatcher` +and run a full pattern-match for every outer binding → O(outer × inner). + +**Fix in `execute_query`**: + +Before `bindings.into_iter().filter(...)`, for each not-body: +1. Run `PatternMatcher::match_patterns(not_body_patterns)` once against `filtered_facts`. +2. Collect results into `HashSet>` keyed on the join variables + only (sorted for determinism). +3. In the filter loop, probe the set in O(1) instead of re-running the matcher. + +**Fix in `evaluate_not_join`**: + +Same pre-compute-once / probe-per-binding pattern for the rules path. + +**Edge cases**: +- Expr-only not bodies (no patterns): keep current behaviour unchanged. +- Not bodies with rule invocations: routed to `execute_query_with_rules` unchanged. + +### #203 — Empty-seed branch evaluation in `apply_or_clauses` + +**File**: `src/query/datalog/executor.rs` (apply_or_clauses) + +**Problem**: `evaluate_branch(branch, bindings.clone(), ...)` seeds each branch with +all incoming bindings → O(seeds × facts × branches). + +**Fix for `WhereClause::Or`**: +1. Evaluate each branch from a single empty-map seed (independent of incoming bindings). +2. Union branch results across all branches (deduplicated — same as today's `seen` set). +3. Hash-join the union back onto incoming `bindings` on the shared variables (variables + present in both the incoming bindings and the branch results). Incoming bindings with + no match are dropped; matching ones are extended with any new variables introduced by + the branch → O(N) probe per binding. + +**Fix for `WhereClause::OrJoin`**: +1. Same empty-seed branch evaluation. +2. Project branch results to `join_vars` only, build `HashMap>` + keyed on the `join_vars` tuple. +3. Hash-join incoming `bindings` against the map on `join_vars`. + +**Correctness invariant**: The hash-join produces the same result as the current +seeded-branch evaluation but in O(N) rather than O(seeds × facts). Incoming bindings +with no match in any branch are dropped, matching Datomic `or`/`or-join` semantics. + +### #204 — Hash-join in `join_with_pattern` + +**File**: `src/query/datalog/matcher.rs` (join_with_pattern) + +**Problem**: For each existing binding, scan all facts for the next pattern → +O(existing_bindings × facts). + +**Fix**: Detect shared variables between the new pattern and existing bindings: + +1. Identify the **join variable**: the first variable in entity, attribute, or value + position of the new pattern that also appears as a key in the existing bindings. + Entity position is checked first (covers the dominant `?e`-join case). +2. If a join variable is found: + - Scan candidate facts for the new pattern once. + - Group into `HashMap>`. + - For each existing binding, look up its join-variable value in the map → O(1). +3. If no join variable is detected (unrelated patterns or fully-literal patterns): + fall back to the current nested-loop path. + +This fix lives entirely in `join_with_pattern`. All callers — `match_patterns`, +`match_patterns_seeded`, `match_patterns_with_hints` — benefit automatically. + +### Tests + +Each fix gets its own test coverage: +- **#202**: `not` and `not-join` shapes at 1k/10k — assert correct result counts; + all existing negation tests pass. +- **#203**: `or` and `or-join` shapes at 1k/10k — union semantics preserved; all + existing or/or-join tests pass. +- **#204**: two-pattern shared-`?e` query at 1k/10k — correct result counts; all + existing join tests pass. + +Full `cargo test` suite passes with no regressions before merging PR 2. + +### Benchmarks + +The existing benchmark groups will show the improvement automatically — no new groups +needed: +- `negation/not_scale`, `negation/not_join_scale` (#202) +- `disjunction/or_scale`, `disjunction/or_join_scale` (#203) +- `aggregation/with_grouped_sum` (#204) + +--- + +## Acceptance Criteria Summary + +| Issue | Criterion | +|-------|-----------| +| #208 | Entity-bound and attribute-bound queries use selective index fetch; `as_of` uses full scan; ≥5 distinct lookups fall back to full scan; new benchmarks added | +| #202 | Negation inner loop pre-computes exclusion set once; `not_scale`/`not_join_scale` benchmarks show sub-linear growth | +| #203 | Or/or-join branches evaluated from empty seed; `or_scale`/`or_join_scale` show sub-linear growth | +| #204 | `join_with_pattern` uses hash-join when shared variable detected; `with_grouped_sum` shows sub-linear growth | + +All: existing 795-test suite passes; no new `{:?}` debug format in test assert messages. diff --git a/src/graph/storage.rs b/src/graph/storage.rs index bc40fd5283..af16e91d1a 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -578,10 +578,10 @@ pub(crate) fn net_asserted_facts(facts: Vec) -> Vec { .collect() } -/// Resolve a FactRef to a Fact using the committed reader (for on-disk facts) +/// Resolve a [FactRef] to a [Fact] using the committed reader (for on-disk facts) /// or the pending facts vector (for in-memory facts with page_id=0). -/// Only used from test-only FactStorage methods and the tests module. -#[cfg(test)] +/// Used by the production index-driven lookup methods (`get_facts_by_entity`, +/// `get_facts_by_attribute`). fn resolve_fact_ref(d: &FactData, fr: FactRef) -> Result { if fr.page_id == 0 { d.facts @@ -601,13 +601,14 @@ fn resolve_fact_ref(d: &FactData, fr: FactRef) -> Result { /// Increment the last byte of a string for prefix upper-bound construction. /// Returns `None` if all bytes are 0xFF (true unbounded scan needed). -/// Only used from test-only FactStorage methods. -#[cfg(test)] +/// Used by the production index-driven lookup methods (`get_facts_by_attribute`). fn next_string_prefix(s: &str) -> Option { let mut bytes = s.as_bytes().to_vec(); for i in (0..bytes.len()).rev() { - if bytes[i] < 0xFF { - bytes[i] += 1; + if let Some(b) = bytes.get_mut(i) + && *b < 0xFF + { + *b += 1; bytes.truncate(i + 1); return String::from_utf8(bytes).ok(); } @@ -615,28 +616,12 @@ fn next_string_prefix(s: &str) -> Option { None } -/// Test-only helpers on FactStorage: index-driven entity/attribute queries. -/// -/// These methods are only used from tests; they are not part of the production -/// query path (the executor uses `get_asserted_facts` + temporal filtering). -#[cfg(test)] +/// Production helpers on FactStorage: index-driven entity/attribute lookups used by the query executor. impl FactStorage { - /// Return all asserted facts valid at the given timestamp. - /// - /// A fact is valid at `ts` when `valid_from <= ts < valid_to` and it is asserted. - pub(crate) fn get_facts_valid_at(&self, ts: i64) -> Result> { - let all = self.get_all_facts()?; - let filtered = all - .into_iter() - .filter(|f| f.is_asserted() && f.valid_from <= ts && ts < f.valid_to) - .collect(); - Ok(filtered) - } - - /// Get all facts for a specific entity (index-driven, test use only). + /// Get all facts for a specific entity (index-driven). pub(crate) fn get_facts_by_entity(&self, entity_id: &EntityId) -> Result> { use crate::storage::index::EavtKey; - let d = self.data.read().unwrap(); + let d = self.data.read().unwrap_or_else(|e| e.into_inner()); let start = EavtKey { entity: *entity_id, @@ -701,10 +686,10 @@ impl FactStorage { Ok(facts) } - /// Get all facts for a specific attribute (index-driven, test use only). + /// Get all facts for a specific attribute (index-driven). pub(crate) fn get_facts_by_attribute(&self, attribute: &Attribute) -> Result> { use crate::storage::index::AevtKey; - let d = self.data.read().unwrap(); + let d = self.data.read().unwrap_or_else(|e| e.into_inner()); // Fallback: no index if d.pending_indexes.aevt.is_empty() && d.committed_index_reader.is_none() { @@ -767,8 +752,15 @@ impl FactStorage { Ok(facts) } +} - /// Get all facts for a specific entity and attribute (test use only). +/// Test-only helpers on FactStorage: for use in tests, not the production query path. +#[cfg(test)] +impl FactStorage { + /// Get all facts for a specific entity and attribute. + /// + /// Note: uses a full scan via `get_all_facts()` rather than an index-driven range scan. + /// For index-driven lookups, use `get_facts_by_entity` and filter by attribute in the caller. pub(crate) fn get_facts_by_entity_attribute( &self, entity_id: &EntityId, @@ -780,6 +772,17 @@ impl FactStorage { .filter(|f| &f.entity == entity_id && &f.attribute == attribute) .collect()) } + /// Return all asserted facts valid at the given timestamp. + /// + /// A fact is valid at `ts` when `valid_from <= ts < valid_to` and it is asserted. + pub(crate) fn get_facts_valid_at(&self, ts: i64) -> Result> { + let all = self.get_all_facts()?; + let filtered = all + .into_iter() + .filter(|f| f.is_asserted() && f.valid_from <= ts && ts < f.valid_to) + .collect(); + Ok(filtered) + } /// Get the current value for an entity-attribute pair (test use only). pub(crate) fn get_current_value( diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 9ea284c8fa..0fab15987d 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -33,6 +33,30 @@ fn query_uses_per_fact_pseudo_attr(query: &DatalogQuery) -> bool { check_clauses(&query.where_clauses) } +/// Recursively collect all `Pattern` clauses from a slice of where clauses, +/// including those nested inside `Not`, `NotJoin`, `Or`, and `OrJoin` bodies. +/// Used by `selective_fact_fetch` to ensure every pattern that references a fact +/// (including not-body patterns) is considered when deciding which indexes to query. +fn collect_all_patterns(clauses: &[WhereClause]) -> Vec { + let mut patterns = Vec::new(); + for clause in clauses { + match clause { + WhereClause::Pattern(p) => patterns.push(p.clone()), + WhereClause::Not(inner) => patterns.extend(collect_all_patterns(inner)), + WhereClause::NotJoin { clauses: inner, .. } => { + patterns.extend(collect_all_patterns(inner)) + } + WhereClause::Or(branches) | WhereClause::OrJoin { branches, .. } => { + for branch in branches { + patterns.extend(collect_all_patterns(branch)); + } + } + WhereClause::RuleInvocation { .. } | WhereClause::Expr { .. } => {} + } + } + patterns +} + /// The result of executing a Datalog command via [`crate::db::Minigraf::execute`]. /// /// Pattern-match on this to distinguish query results from write confirmations: @@ -294,9 +318,9 @@ impl DatalogExecutor { /// The three steps above are paid exactly once per `execute_query` / /// `execute_query_with_rules` call. /// - /// **Post-1.0 backlog**: Use the on-disk B+tree indexes (EAVT/AEVT/AVET/VAET) for - /// selective attribute/entity lookups instead of the full `get_all_facts()` scan (step 1). - /// Also investigate caching the `net_asserted_facts()` result and invalidating on write (step 2). + /// Step 1 uses selective index-backed fetches when query patterns bind concrete entities + /// or attributes (up to 4 distinct lookups); falls back to `get_all_facts()` otherwise. + /// Step 2 (caching `net_asserted_facts()`) remains a future optimisation opportunity. fn filter_facts_for_query(&self, query: &DatalogQuery) -> Result> { let now = self.read_now(); @@ -306,7 +330,19 @@ impl DatalogExecutor { } (Some(facts), None) => facts.iter().cloned().collect(), (None, Some(as_of)) => self.storage.get_facts_as_of(as_of)?, - (None, None) => self.storage.get_all_facts()?, + (None, None) => { + // Selective fetch is only safe when no rule invocations are present — + // rules require the full fact base to evaluate correctly. + if !query.uses_rules() { + let patterns = collect_all_patterns(&query.where_clauses); + match self.selective_fact_fetch(&patterns, 4) { + Some(facts) => facts, + None => self.storage.get_all_facts()?, + } + } else { + self.storage.get_all_facts()? + } + } }; let tx_filtered = source_facts; @@ -337,6 +373,78 @@ impl DatalogExecutor { Ok(Arc::from(valid_filtered)) } + /// 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)`. + fn selective_fact_fetch(&self, patterns: &[Pattern], threshold: usize) -> Option> { + use std::collections::HashSet; + + let mut entity_ids: HashSet = HashSet::new(); + 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); + } + } + _ => {} + } + // Bound attribute: non-variable keyword + if let AttributeSpec::Real(EdnValue::Keyword(attr)) = &pattern.attribute { + attributes.insert(attr.clone()); + } + } + + let total = entity_ids.len() + attributes.len(); + if total == 0 || total > threshold { + return None; + } + + // Dedup key: (entity uuid, attribute string, tx_count) — avoids Value debug formatting. + let mut seen: HashSet<(uuid::Uuid, String, u64)> = HashSet::new(); + let mut all_facts: Vec = Vec::new(); + + for uid in &entity_ids { + match self.storage.get_facts_by_entity(uid) { + Ok(facts) => { + for fact in facts { + let key = (fact.entity, fact.attribute.clone(), fact.tx_count); + if seen.insert(key) { + all_facts.push(fact); + } + } + } + Err(_) => return None, + } + } + + for attr in &attributes { + match self.storage.get_facts_by_attribute(attr) { + Ok(facts) => { + for fact in facts { + let key = (fact.entity, fact.attribute.clone(), fact.tx_count); + if seen.insert(key) { + all_facts.push(fact); + } + } + } + Err(_) => return None, + } + } + + Some(all_facts) + } + /// Execute a query: find matching facts and return specified variables fn execute_query(&self, query: DatalogQuery) -> Result { // Check if query uses rules @@ -4489,3 +4597,88 @@ mod expr_eval_tests { assert_eq!(row_b100.get("__win_2"), Some(&Value::Integer(100))); } } + +#[cfg(test)] +mod selective_lookup_tests { + use crate::graph::FactStorage; + use crate::query::datalog::executor::DatalogExecutor; + + fn make_db_with_entities(n: 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!(r#"[:e{i} :name "entity{i}"]"#, i = i)); + 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 + } + + #[test] + fn entity_bound_query_returns_correct_results() { + let exec = make_db_with_entities(100); + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + r#"(query [:find ?n :where [:e5 :name ?n]])"#, + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { + assert_eq!(results.len(), 1, "expected exactly 1 result for entity :e5"); + assert_eq!( + results[0][0], + crate::graph::types::Value::String("entity5".to_string()) + ); + } else { + panic!("expected QueryResults"); + } + } + + #[test] + fn attribute_bound_query_returns_correct_results() { + let exec = make_db_with_entities(100); + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?e ?v :where [?e :val ?v]])", + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { + assert_eq!( + results.len(), + 100, + "expected 100 results for :val attribute scan" + ); + } else { + panic!("expected QueryResults"); + } + } + + #[test] + fn as_of_query_still_works_after_change() { + let exec = make_db_with_entities(10); + let result = exec + .execute( + crate::query::datalog::parser::parse_datalog_command( + "(query [:find ?n :where [?e :name ?n] :as-of 1])", + ) + .unwrap(), + ) + .unwrap(); + if let crate::query::datalog::executor::QueryResult::QueryResults { results, .. } = result { + assert!(!results.is_empty(), "expected results from as-of 1 query"); + } else { + panic!("expected QueryResults"); + } + } +}