Repository navigation
perf: attribute scan is unbounded to end of AEVT index for attributes ending in a 0xBF/0x7F byte #381
Description
Summary
FactStorage::get_facts_by_attribute (src/graph/storage.rs:688 on main) bounds its AEVT range with next_string_prefix(attribute), which increments the attribute's last byte. When the result is not valid UTF-8, it returns None (storage.rs:603), and the committed scan runs from the attribute to the end of the whole AEVT index, resolving every fact before post-filtering (storage.rs:709, :742).
This happens when the attribute's last byte is:
0x7F, or0xBF, the final byte of roughly 1 in 64 non-ASCII code points, e.g.:丿(U+4E3F) or:¿.
Results stay correct because of the post-filter, but [?e :丿 ?v] costs O(everything after :丿 in AEVT) instead of O(facts for :丿). It grows with database size, so applications with CJK or other non-ASCII attribute names are the ones affected.
There is a second, smaller waste even for ordinary names: the range [:a, :b) also covers prefix siblings (:ab, :a/b). Their facts and history are resolved and then thrown away.
Evidence
Found in review of #380 (#323). The same bug in the new entity path, get_facts_by_entity_attribute_indexed, measured 130× slower on a 20k-entity checkpointed file (252 µs → 32.8 ms) for [:e/a0 :丿 ?v]. #380 fixed that path; the attribute-scan path predates it and is unchanged.
Fix
Use the exact successor format!("{attribute}\0") as the range end. It is the smallest string that sorts after attribute and is always valid UTF-8. This gives an exact range, removes the None branch, and stops resolving prefix siblings. #380 applies the same pattern in get_facts_by_entity_attribute_indexed, and its test entity_attribute_indexed_committed_range_is_bounded_for_any_attribute (a mock CommittedIndexReader that records the range bounds) can be adapted.
Once no callers remain, next_string_prefix can be removed.
Refs #323
Activity
docs(roadmap): make v2.0.2 the final v2.x release, split v3.0.0/v3.1.0 (
Merge pull request #412 from project-minigraf/merge/main-into-v3
release: v2.0.2 — final planned v2.x release