Repository navigation
perf: point query on a bound entity scans the entity's whole version history — O(retract/reassert count), not O(live facts) #323
Description
Summary
A point query on a bound entity costs O(total versions ever written for that
entity), not O(live facts). An entity whose attribute is retracted and
reasserted N times answers a :find for its single live value ~N times slower
than a freshly written one, at identical graph size. Any "current value of a
mutable cell" pattern therefore degrades linearly over its own lifetime.
Reproducer
One entity, one attribute, retracted and reasserted in a loop. Exactly one
fact is live at every measurement. Filler is checkpointed and constant within
each arm; the query is (query [:find ?v :where [:e/hot :hash ?v]]), median of
20 calls after a checkpoint.
db.execute(f'(retract [[:e/hot :hash "{prev}"]])')
db.execute(f'(transact {{:valid-from "{TS}"}} [[:e/hot :hash "{cur}"]])')| chain depth | 10k filler | 100k filler |
|---|---|---|
| 1 | 0.128 ms | 0.115 ms |
| 100 | 0.426 ms | 0.463 ms |
| 500 | 1.797 ms | 1.820 ms |
| 1000 | 3.475 ms | 3.522 ms |
| 2000 | 6.782 ms | 7.008 ms |
| 4000 | 13.826 ms | 13.514 ms |
107.7x / 117.3x growth, dead linear in depth at roughly 3.4 µs per dead
version. A 10x change in total graph size moves the curve by noise, so this is
the entity's own version count and nothing else.
Mechanism
DatalogExecutor's bound-entity path (src/query/datalog/executor.rs:416)
calls get_facts_by_entity(uid) and pushes every returned fact into
all_facts, deduping on (entity, attribute, tx_count, asserted). Valid-time
and assertion filtering happen downstream of that materialization.
FactStorage::get_facts_by_entity (src/graph/storage.rs:622) range-scans
EAVT from (entity, "", i64::MIN, i64::MIN, 0) to the next entity id. The
EavtKey includes valid_from, valid_to and tx_count, so every
retract/reassert cycle adds another key under the same entity, and each hit
costs a resolve_fact_ref — a loader.resolve(fr) page load for committed
facts.
So the scan returns the entity's entire history and the executor pays a page
resolve per dead version before discarding all of them.
Why this bites
The pattern it penalises is "a fixed ident holding a mutable current value" —
watermarks, cursors, counters, config cells. In
project-minigraf/temporal_reasoning three such idents are updated once per
ingested commit, so each is O(commits processed) to read and the run is O(N²) in
that term. Measured there: the query component of the per-commit update grows
22.80x over 6000 cycles while being invariant across a 50x graph-size sweep
(1.12 / 1.12 / 1.09 s at 100k / 1M / 5M filler).
Every one of those queries wants exactly one live fact.
Possible directions
Offered as context, not as a prescription — the right fix depends on internals I
can only read from outside.
- Push the "currently live" predicate into the scan. The common case is a
plain[:e/x :attr ?v]with no:as-of/:valid-at, i.e. only
valid_to IS NULLassertions can match. If liveness were part of the key
ordering or a skip condition, the scan could stop at the live tip. - A live-tip index. The feat(wasi): Phase 8.1b — wasm32-wasip1 server-side WASM support #152 / perf: avoid per-EAV allocations in net assertion #236 pattern in the downstream repo — a
companion structure keyed by(entity, attribute)pointing at the current
version — replacing a scan with a lookup. - Bound the scan when the query has no temporal clause, leaving the full
history walk for queries that actually ask for it.
Related in spirit to #248 and #250 (pushing predicates to the earliest valid
position), applied to the temporal predicate rather than to not / or.
Notes
- Version measured: minigraf 1.2.3, release build via the packaged
libminigraf_ffi.so. retractandtransactthemselves are flat in chain depth (measured 1.08x
and 1.16x over 6000 cycles) — the growth is entirely on the read path.
Activity
adityamukho commentedon Sep 19, 2026
Downstream impact measured on a real workload: ~⅓ of temporal_reasoning's ingestion wall clock
Measured on minigraf 2.0.0 with a full git-history ingestion (957 commits) by project-minigraf/temporal_reasoning. Its ingestion retracts and re-asserts the same entities' facts over and over as lineage moves, so heavily rewritten entities build up long version chains. Details: project-minigraf/temporal_reasoning#239 (issuecomment-5740728463).
Point queries on a bound entity
Bound-entity point queries (
[<ident> :attr ?v]) account for 1,086 s of a 3,331 s run (32.6%), across about 2.5M calls. Timed against every one of the 3,989 code entities on the finished graph:[<ident> :introduced-by ?c][<ident> :modified-in ?c]Two different attributes cost the same on the same entity, and the slowest entities are the ones rewritten most. That fits this issue's mechanism: cost follows the entity's total version history, not the attribute's live facts. A synthetic bench over entities that were written once and never retracted measured 0.06 ms/call on graphs of 100k–5M facts, which is 7–16x lower than the real per-call average.
Possibly beyond this issue: attribute-only scans look history-bound too
The same finished graph (median of 5 runs):
[?e :introduced-by ?c][?e :modified-in ?c][?e :ident ?i](rarely rewritten)The first two queries return about the same number of rows as
:identbut take roughly 30x longer. Those two attributes are the heavily churned ones. That suggests the attribute path (get_facts_by_attribute) also pays for dead versions. I haven't traced that in the source, so please treat it as an observation rather than a diagnosis. It matters downstream because it rules out the usual workaround of swapping a loop of point queries for one set-at-a-time scan: on this graph the scan costs as much as the loop it would replace.What this blocks
temporal_reasoning#239 is parked on this issue. The only fix available downstream is an in-process write-through cache, which carries real invalidation risk. A fix here would remove about a third of ingestion time with no downstream changes. The retract path looks affected too: 223k retracts at 1.38 ms each, another 9.3% of the run.
perf: narrow bound-entity point queries to the queried attribute (#323 …
perf: bound attribute scans to exactly the queried attribute (#381) (#…
adityamukho commentedon Sep 26, 2026
Closing as mitigated on the v2.x line. The rest of the work is tracked in #379 (v3.0.0).
Shipped on
main(in the next v2.x release, v2.3.0):[:e :attr ?v]) range-scan only(e, :attr)in EAVT, so other attributes' history is never read. Reading a rarely changed attribute of a heavily rewritten entity drops from 4.58 ms to 19 µs at 2,000 rewrites. Reading the rewritten attribute itself and attribute scans are about 1.35–1.4× faster.[?e :attr ?v]) are bounded to exactly the queried attribute. Before this, attributes whose last byte is 0x7F/0xBF (e.g.:丿) scanned to the end of AEVT. A sparse:丿scan drops from 45.4 ms to 251 µs.Still open: a heavily rewritten attribute costs O(its history) per read. v7 index keys carry neither the value nor the asserted flag, so liveness can only be decided after resolving every record. The structural fix needs the v8 keys, which exist only on the
v3branch. It is tracked in #379, which computes net-assert on the keys before resolving so resolve cost becomes O(live).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