From 387ff86075002257cdaa7e404730ae2c7ba367ce Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 26 Sep 2026 10:00:04 +0530 Subject: [PATCH] perf: bound attribute scans to exactly the queried attribute (#381) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit get_facts_by_attribute ended its AEVT range at next_string_prefix(attr), which increments the last byte. For attributes ending in 0x7F or 0xBF (e.g. `:丿`, `:ÿ`) that is not valid UTF-8, so the committed scan ran to the end of the AEVT index. It also covered prefix siblings (`:ab` for `:a`). End the range at `attribute + "\0"`, the exact successor, as #380 does for the entity path. Remove the now-unused next_string_prefix. Sparse `:丿` scan (100 of 40.1k facts, checkpointed): 45.4 ms -> 251 µs. Closes #381 Refs #323 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- CHANGELOG.md | 1 + CLAUDE.md | 2 +- README.md | 2 +- docs/TEST_COVERAGE.md | 4 +- src/graph/storage.rs | 155 ++++++++++++++++++++++-------- tests/point_query_history_test.rs | 31 ++++++ 6 files changed, 150 insertions(+), 45 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index f5ad6d863e..4cb3be6768 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -10,6 +10,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Performance - **Bound-entity point queries no longer pay for other attributes' history (#323).** `[:e :attr ?v]` now range-scans only `(e, :attr)` in the EAVT index instead of every record the entity has ever written. Reading a rarely changed attribute of a heavily rewritten entity no longer slows down as that entity's history grows: with 2,000 retract/reassert cycles on another attribute of the same entity, it drops from 4.58 ms to 19.0 µs. Reading the heavily rewritten attribute itself, and attribute scans (`[?e :attr ?v]`), are about 1.35–1.4× faster (4.64 ms → 3.36 ms), from cheaper net-assert grouping and removing a redundant dedup pass. The file format is unchanged. +- **Attribute scans are bounded to exactly the queried attribute (#381).** `[?e :attr ?v]` computed the end of its AEVT range by incrementing the attribute's last byte. For attributes whose last byte is `0x7F` or `0xBF` — including about 1 in 64 non-ASCII characters, such as `:丿` or `:ÿ` — the result was not valid UTF-8, so the scan ran to the end of the whole AEVT index and read every later fact before filtering. It also read facts for prefix siblings (`:ab`, `:a/b` when scanning `:a`). The range now ends at `attribute + "\0"`, which covers exactly one attribute. Scanning 100 `:丿` facts in a checkpointed file with 40,000 facts on neighbouring attributes drops from 45.4 ms to 251 µs. Results are unchanged. ### Fixed diff --git a/CLAUDE.md b/CLAUDE.md index f0359ec370..78c9a85788 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -167,7 +167,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1173 tests passing** (1165 passing, 8 ignored; unit + integration + doc). +**1176 tests passing** (1168 passing, 8 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/README.md b/README.md index 93af3e1e0f..874758f154 100644 --- a/README.md +++ b/README.md @@ -92,7 +92,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1173 tests +cargo test # run 1176 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 86fd20e154..beb7cb9c04 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-09-26 with `cargo test` -**Result**: 1,165 passing tests and 8 ignored tests (1,173 total) +**Result**: 1,168 passing tests and 8 ignored tests (1,176 total) -The v2.0.1 suite covers the public database API, the Datalog engine, storage and recovery paths, and the v2.0.0 locking and structured-error-code changes, plus v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Since v2.0.1, `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). +The v2.0.1 suite covers the public database API, the Datalog engine, storage and recovery paths, and the v2.0.0 locking and structured-error-code changes, plus v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Since v2.0.1, `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). ### Covered Areas diff --git a/src/graph/storage.rs b/src/graph/storage.rs index e4fbf0491b..82d54d71b7 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -595,23 +595,6 @@ 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). -/// 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 let Some(b) = bytes.get_mut(i) - && *b < 0xFF - { - *b += 1; - bytes.truncate(i + 1); - return String::from_utf8(bytes).ok(); - } - } - None -} - /// Production helpers on FactStorage: index-driven entity/attribute lookups used by the query executor. impl FactStorage { /// Get all facts for a specific entity (index-driven). @@ -771,41 +754,28 @@ impl FactStorage { valid_to: i64::MIN, tx_count: 0, }; - let end_opt: Option = next_string_prefix(attribute).map(|next_attr| AevtKey { - attribute: next_attr, + // Exact successor of `attribute` (see `get_facts_by_entity_attribute_indexed`): + // `[start, end)` holds exactly this attribute, never prefix siblings such as + // `:ab` for `:a`, and is valid UTF-8 for any attribute (#381). + let end = AevtKey { + attribute: format!("{attribute}\0"), 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 { + // Pending: AEVT keys for the exact attribute are contiguous from `start`. + for (_, &fr) in d.pending_indexes.aevt.range(start.clone()..end.clone()) { facts.push(resolve_fact_ref(&d, fr)?); } - // Committed + // Committed: on-disk B+tree range scan over exactly this attribute; the + // post-filter is a cheap guard, not something the range relies on. 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 { + for fr in reader.range_scan_aevt(&start, Some(&end))? { let fact = resolve_fact_ref(&d, fr)?; if &fact.attribute == attribute { facts.push(fact); @@ -2346,4 +2316,107 @@ mod tests { ); } } + + #[test] + fn attribute_committed_range_is_bounded_for_any_attribute() { + use crate::storage::CommittedIndexReader; + use crate::storage::index::{AevtKey, AvetKey, EavtKey, FactRef, VaetKey}; + use std::sync::{Arc, Mutex}; + + struct RecordingReader { + aevt_bounds: Mutex)>>, + } + impl CommittedIndexReader for RecordingReader { + fn range_scan_eavt( + &self, + _: &EavtKey, + _: Option<&EavtKey>, + ) -> anyhow::Result> { + Ok(vec![]) + } + fn range_scan_aevt( + &self, + start: &AevtKey, + end: Option<&AevtKey>, + ) -> anyhow::Result> { + self.aevt_bounds + .lock() + .unwrap() + .push((start.clone(), end.cloned())); + Ok(vec![]) + } + fn range_scan_avet( + &self, + _: &AvetKey, + _: Option<&AvetKey>, + ) -> anyhow::Result> { + Ok(vec![]) + } + fn range_scan_vaet( + &self, + _: &VaetKey, + _: Option<&VaetKey>, + ) -> anyhow::Result> { + Ok(vec![]) + } + } + + let reader = Arc::new(RecordingReader { + aevt_bounds: Mutex::new(Vec::new()), + }); + let storage = FactStorage::new(); + storage.set_committed_index_reader(reader.clone()); + + for attr in [":plain", ":\u{4e3f}", ":\u{bf}", ":a\u{7f}"] { + storage.get_facts_by_attribute(&attr.to_string()).unwrap(); + } + + let bounds = reader.aevt_bounds.lock().unwrap(); + assert_eq!(bounds.len(), 4, "one committed scan per lookup"); + for (start, end) in bounds.iter() { + let end = end + .as_ref() + .expect("committed AEVT scan must have an upper bound"); + assert!(start < end, "range must be non-empty"); + // No other attribute may sort between start and end. + let sibling = AevtKey { + attribute: format!("{}x", start.attribute), + ..start.clone() + }; + assert!( + sibling >= *end, + "prefix sibling must fall outside the range" + ); + } + } + + #[test] + fn attribute_scan_excludes_prefix_siblings_and_non_ascii_neighbours() { + let storage = FactStorage::new(); + let e = uuid::Uuid::from_u128(7); + for attr in [ + ":a", + ":ab", + ":a/b", + ":\u{4e3f}", + ":\u{4e40}", + ":\u{bf}", + ":\u{c0}", + ] { + storage + .transact( + vec![(e, attr.to_string(), Value::String(attr.to_string()))], + None, + ) + .unwrap(); + } + for attr in [":a", ":\u{4e3f}", ":\u{bf}"] { + let facts = storage.get_facts_by_attribute(&attr.to_string()).unwrap(); + assert_eq!(facts.len(), 1, "exactly one fact for the attribute"); + assert!( + facts.iter().all(|f| f.attribute == attr), + "no sibling facts" + ); + } + } } diff --git a/tests/point_query_history_test.rs b/tests/point_query_history_test.rs index 26878311bc..68d9ff3bc1 100644 --- a/tests/point_query_history_test.rs +++ b/tests/point_query_history_test.rs @@ -207,3 +207,34 @@ fn same_transaction_multi_window_matches_full_scan() { let r = same_as_full_scan(&db, "?v", ":any-valid-time", "[:e/w :x ?v]"); assert_eq!(r.len(), 2, "both windows' values must be returned"); } + +/// #381 — attribute-bound scans (`[?e :a ?v]`) over a checkpointed file return exactly +/// the queried attribute, including non-ASCII names whose last UTF-8 byte is 0xBF +/// (`:丿`, `:ÿ`) and ordinary names with prefix siblings (`:a` vs `:ab`, `:a/b`). +#[test] +fn attribute_scan_exact_for_non_ascii_and_prefix_siblings_file_backed() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + let attrs = [":a", ":ab", ":a/b", ":丿", ":丿x", ":乀", ":ÿ", ":ÿx", ":Ā"]; + let db = Minigraf::open(&path).unwrap(); + for (i, attr) in attrs.iter().enumerate() { + db.execute(&format!("(transact [[:e/c{i} {attr} \"c{i}\"]])")) + .unwrap(); + } + db.checkpoint().unwrap(); + // Pending on top of committed. + for (i, attr) in attrs.iter().enumerate() { + db.execute(&format!("(transact [[:e/p{i} {attr} \"p{i}\"]])")) + .unwrap(); + } + for (i, attr) in attrs.iter().enumerate() { + let r = same_as_full_scan(&db, "?e ?v", "", &format!("[?e {attr} ?v]")); + assert_eq!( + r.len(), + 2, + "one committed and one pending fact per attribute" + ); + assert!(r.iter().any(|row| row.contains(&format!("\"c{i}\"")))); + assert!(r.iter().any(|row| row.contains(&format!("\"p{i}\"")))); + } +}