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

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -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

Expand Down
2 changes: 1 addition & 1 deletion CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -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.
Expand Down
2 changes: 1 addition & 1 deletion README.md
Original file line number Diff line number Diff line change
Expand Up @@ -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
```

Expand Down
4 changes: 2 additions & 2 deletions docs/TEST_COVERAGE.md
Original file line number Diff line number Diff line change
Expand Up @@ -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

Expand Down
155 changes: 114 additions & 41 deletions src/graph/storage.rs
Original file line number Diff line number Diff line change
Expand Up @@ -595,23 +595,6 @@ fn resolve_fact_ref(d: &FactData, fr: FactRef) -> Result<Fact> {
}
}

/// 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<String> {
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).
Expand Down Expand Up @@ -771,41 +754,28 @@ impl FactStorage {
valid_to: i64::MIN,
tx_count: 0,
};
let end_opt: Option<AevtKey> = 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<FactRef> = 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);
Expand Down Expand Up @@ -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<Vec<(AevtKey, Option<AevtKey>)>>,
}
impl CommittedIndexReader for RecordingReader {
fn range_scan_eavt(
&self,
_: &EavtKey,
_: Option<&EavtKey>,
) -> anyhow::Result<Vec<FactRef>> {
Ok(vec![])
}
fn range_scan_aevt(
&self,
start: &AevtKey,
end: Option<&AevtKey>,
) -> anyhow::Result<Vec<FactRef>> {
self.aevt_bounds
.lock()
.unwrap()
.push((start.clone(), end.cloned()));
Ok(vec![])
}
fn range_scan_avet(
&self,
_: &AvetKey,
_: Option<&AvetKey>,
) -> anyhow::Result<Vec<FactRef>> {
Ok(vec![])
}
fn range_scan_vaet(
&self,
_: &VaetKey,
_: Option<&VaetKey>,
) -> anyhow::Result<Vec<FactRef>> {
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"
);
}
}
}
31 changes: 31 additions & 0 deletions tests/point_query_history_test.rs
Original file line number Diff line number Diff line change
Expand Up @@ -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}\""))));
}
}
Loading