Repository navigation
perf: attribute+value patterns scan the whole attribute; AVET index is never read #518
Description
Problem
A pattern with a constant attribute and a constant value, such as [?e :p/name "name-42"], scans every committed fact of the attribute instead of seeking the AVET index. Its cost grows with the attribute's size, not with the answer.
Found by the soak test (#392) on v3 (--profile bench, one matching fact):
| Live facts | :p/name facts |
[?e :p/name "name-N"] p50 |
[:eN ?a ?v] (EAVT) p50 |
|---|---|---|---|
| 20K (debug) | 3.6K | 58 ms | 0.3 ms |
| 1M | 178K | 517 ms | 0.05 ms |
| 1.35M | 240K | 761 ms | 0.06 ms |
Cause
optimizer::select_index picks IndexHint::Avet for this shape, and v8 files keep an AVET tree (meta.avet_root), but CommittedReader has no attribute-and-value lookup. The executor falls back to facts_for_attribute, then filters by value. The AVET tree is written at every checkpoint and checked by verify(), but no query reads it.
Ask
Add an attribute-and-value read to CommittedReader (an AVET prefix scan over a v) and use it for this pattern shape, including refs (IndexHint::Avet for a bound ref value as well). Add a benchmark at 1M facts (#394). Uniqueness lookups ([?e :user/email "…"]) are a common agent-memory and app pattern.
Activity
adityamukho commentedon Oct 10, 2026
Confirmed in code:
Matcher::match_pattern_with_hint(&self, pattern, _hint)(src/query/datalog/matcher.rs:305) ignores the hint. The same applies to VAET: a reverse-ref pattern[?e :p/ref #uuid "…"]also scans the attribute. The AVET and VAET trees are written at each checkpoint and walked byverify(), but no query reads them.adityamukho commentedon Oct 10, 2026
At 10M live facts (1.78M
:p/namefacts, soak test #519,--profile bench):[?e :p/name "name-N"]p50 5.8 s, p99 7.5 s; EAVT point query p50 52 µs.adityamukho commentedon Oct 10, 2026
v2.0.4 behaves the same (soak test on
main, #520):[?e :p/name "name-N"]p50 0.9 s at 2M facts. v2.x gets only data-integrity and security fixes, so this is for v3 only.adityamukho commentedon Oct 11, 2026
Parked on branch
perf/518-avet-lookup(fe545dc, based onv3a16f385) until the streaming engine (#473) is done.What the branch does (no format change):
CommittedReader/ScangainAttributeValue(attr, &Value)andAttributeKind(attr, ValueKind), read as AVET prefix scans (keys::attribute_value_prefix,attribute_string_prefix,attribute_kind_prefix). Pending facts are filtered within the attribute's AEVT range.selective_fact_fetchmaps a constant to the lookups covering every valuematch_componentaccepts: a keyword also matches a ref to the entity it names, a UUID also matches keyword values (whole keyword range), a float reads every float of the attribute (epsilon match). An attribute that also appears with a variable value falls back to the whole attribute.tests/live_reads_test.rschecks the narrow reads against whole-attribute reads (cross-type,:as-of, retractions, reopen).Perf envelope at 1M facts (busy machine, to be re-run idle):
attribute_value274 ms → 11 µs p50 (137 → 4 MiB),join_3_scan1.95 s → 1.53 s,attribute_scanunchanged.On revisit: #473's
Scanoperator should call these reads instead ofselective_fact_fetch. Then rebase ontov3, re-run the envelope at 100K/1M/10M on an idle machine, updatedocs/BENCHMARKS.md(the #518 note and table rows) andCHANGELOG.md, and fix the test count.adityamukho commentedon Oct 14, 2026
Fixed on v3 by PR #588 (#544 PR 1):
[?e :a C]reads the AVET range of C in the new streaming engine. 1M facts, #394 envelope: 344 ms → 20 µs p50, 142 → 3 MiB peak RSS.adityamukho commentedon Oct 14, 2026
Closed as covered. What #588 did not finish is tracked here:
[?e :a :k],[?e :p/ref #uuid "…"], float within epsilon) read AVET (and VAET for a ref value with the attribute unbound): streaming engine 2/9: operator core, Scan and oracle harness (#473) #544 PR 2 (plan step 9,docs/superpowers/plans/2026-10-14-544-operator-core.md). Until then these queries run on the executor, unchanged.docs/BENCHMARKS.mdperf: attribute+value patterns scan the whole attribute; AVET index is never read #518 note and rows: streaming engine 2/9: operator core, Scan and oracle harness (#473) #544 PR 3 (plan step 11), then again after every sub-issue and finally in streaming engine 9/9: remove the old executor, measure, docs (#473) #551.IndexNestedLoopJoin): streaming engine 3/9: IndexNestedLoopJoin and HashJoin (#473) #545.Branch
perf/518-avet-lookupstays parked for reference until the streaming engine (#473) is done.