adityamukho · Oct 27, 2026 · Oct 27, 2026 · Oct 27, 2026
@@ -122,6 +122,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 
 ### Internal
 
+- **Projected entity UUIDs share DICT tree reads** (#530). Projection resolves up to 1,024 committed ids together, walking dense dictionary ranges with the existing leaf cursor and using scalar exact reads for sparse/small batches. Bounded stack hints keep query-cache insertion and memory charges in projection order; pending ids stay in memory, failed speculative reads fall back to scalar conversion, and each pull still releases committed lookup maps. No file-format or configuration change. The focused 1M-fact scan has 48.2% lower p50 latency (262 → 136 ms); `docs/BENCHMARKS.md` records paired runs, cutoff costs and repeated-ref variability.
 - **Committed reads hide superseded history on index keys** (#379). A query's committed facts are now reduced to the ones that survive net-assert (each fact's assertion from its newest transaction, unless that transaction retracted it; #435) while walking the index keys, before any fact is built. Only surviving entries are decoded and translated through the dictionary. A transaction that retracted a triple hides everything older in it, and a long run of hidden entries is skipped with one `seek`. `:as-of N` point and attribute queries now take the same index path instead of reading every fact in the file. On a checkpointed file with 2,000 superseded values, a point query takes 1.03 ms instead of 4.61 ms, an attribute scan 1.24 ms instead of 5.87 ms, and an `:as-of` point query 23 µs instead of 5.6 ms (at depth 1). Results are unchanged: the executor still applies net-assert to committed and pending facts together, and a pending fact is always newer than a committed one.
 - **B+tree reads no longer follow leaf sibling links** (v8 storage format, PR 1 of 5; #374). Every index scan uses a cursor that walks down from the root and keeps the path, with a forward `seek` that climbs only as far as needed. This prepares for copy-on-write index pages, which cannot keep 
8000
sibling links. The file format and query results are unchanged. Concurrent 100k-fact scans take 25–37 % less time and checkpointing after one fact at 10k facts 9 % less; single point lookups and attribute scans are 2–6 % slower (about 0.4 µs per lookup). A corrupted child pointer now fails with STG-013 (wrong page type) or INT-049 (cycle) instead of following a bad link.
 

@@ -119,8 +119,8 @@ cargo run < demos/demo_negation.txt
    - `index.rs`: pending (uncheckpointed) EAVT/AEVT keys over UUIDs and strings, `encode_value`; `index/verification.rs`: Kani proofs of `encode_value` (`#[cfg(kani)]`, #627)
    - `keys.rs`: byte-comparable v8 keys (FDB integers, value tags, `tx↓`, FOREVER), DICT keys, `MAX_VALUE_BYTES`, `MAX_IDENT_BYTES`; sets (#316): tag `0x08`, element encoding (`set_elements`: each element's key encoding, sorted) inline up to 64 bytes, else `LongSet` in a value page, `decode_set`, `set_bytes_bound` (the WAL's id-free size bound); `keys/verification.rs`: Kani proofs that the key encoders preserve order (`#[cfg(kani)]`, #627; `kani.yml` runs them on encoder PRs and nightly)
    - `node.rs`: prefix-compressed leaf and shortest-separator internal node codecs
-   - `btree.rs`: On-disk B+tree over byte keys (`build_btree`, `cow_update` (copy-on-write inserts and deletes; an emptied leaf or node leaves its parent, an emptied tree is root 0; #550) and `cow_insert`, `LeafCursor` with `seek`, `prefix_scan`, `get`, `MutexStorageBackend`)
-   - `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values) and `Encoder` (checkpoint-time id assignment and key building)
+   - `btree.rs`: On-disk B+tree over byte keys (`build_btree`, `cow_update` (copy-on-write inserts and deletes; an emptied leaf or node leaves its parent, an emptied tree is root 0; #550) and `cow_insert`, `LeafCursor` (with `seek`), `prefix_scan`, `get`, `MutexStorageBackend`)
+   - `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values; `uuids_of` walks dense id batches with `LeafCursor` and uses exact scalar reads for sparse/small batches, #530) and `Encoder` (checkpoint-time id assignment and key building)
    - `value_pages.rs`: append-only value pages for strings over 64 bytes and sets whose element encoding is over 64 bytes (#316; DICT dedup compares bytes, `long_bytes`/`find_long_bytes`)
    - `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`, `KeySource`); `live_facts` and the resumable `live_keys` decide net-assert on index keys (#379) among the versions a `TxBound` keeps; `tx_order` (cached per reader), `last_tx_at`, `tx_runs` over the DICT's transactions (#551)
    - `verify.rs`: integrity walk for `Minigraf::verify` (tree order, index digests, DICT, page accounting) and the source choice for `rebuild_indexes` (#373)
@@ -148,7 +148,7 @@ cargo run < demos/demo_negation.txt
    - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute`; `Entity` and `Val(Ref)` fit each other's slots, bind mistakes are `API-022`/`023`/`024` (#181); a `:limit $n` or `:offset $o` slot takes `Val(Integer(n >= 0))` (`resolve_count_slot`, #306)
    - `magic_sets.rs`: Magic-sets rewriting for demand-driven recursive rule evaluation (not applied to rules with `not`/`not-join`)
 
-3a. **`src/query/engine/`** — Streaming query engine (#473), runs every query (#551): `plan.rs` (the operator tree of every query, or the executor's error code for it: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a magic-set head constant is `HeadArg::Const`), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; an `or` branch or a `not` body is planned as a `:where` is; a clause list with no pattern first starts from `Seed`; a constant no cell equals is `Term::Never`, a scan that reads nothing; `:as-of` resolved when the query opens (`Snapshot::tx_bound`: a counter bound when `tx_id` rises with `tx_count`, else `TxBound::Timestamp`: committed `tx_count` ranges and pending `tx_id <= t`); a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, or, under a constant attribute and entity not constant, its value (#721: per outer row the AVET ranges of the values that join-equal it and the attribute's pending facts with its key, read once per query in `IdSpace::probes`; an entity cell needs the keyword naming it, known only where the query made the entity from a keyword (rule heads, magic seeds), else the join becomes the planner's `HashJoin`); `HashJoin` otherwise, and on a relation; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `collect.rs` (`CollectSet`, #316: `[(collect-set ?e :a) ?s]` per row probes `[e :a ?v]` as an `IndexNestedLoopJoin` does and binds the values as one set, `#{}` when none, metered; `Expr::CollectSet`, parsed only as a whole binding clause), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `sort.rs` (`Sort`, #306: the `:find` columns as values, in the full order of `:order-by` — its keys, then every other `:find` column ascending, by `datalog::aggregate::row_order`/`value_order`; under a `:limit` a heap of the best `offset + limit` rows; reads its whole input, dropping the DICT lookups after each batch, metered; its rows turned back into cells only as returned), `limit.rs` (`Limit`, #306: skips `offset` rows, passes on at most `limit`, then closes its child so nothing below reads more; planned after the last step, after `Builder::finish`, and after `Sort`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare; `:distinct` adds `DistinctFind` after aggregates/windows and before sorting/pagination, keyed on final `:find` columns by aggregate-group equality, with canonical float zero/NaN output including set elements, #493), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `meter.rs` (#549: one `Meter` per query, shared by every holder of state through a `Held` — hash join build sides, `not`/`or` tables, distinct sets, aggregate groups, window rows, rule relations and their temporaries, `IdSpace`, the set a `CollectSet` builds; each entry charged by a per-entry estimate including retained set elements and strings before it is inserted, containers grown with `try_reserve`, released on `rewind`/`close`/drop; over `OpenOptions::query_memory_limit`, or a refused allocation, is `QRY-012`; `Stream::close` drops the operator tree, keeping its counters). `mod.rs`: `Operator` (`next_batch`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` run every query on it: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it.
+3a. **`src/query/engine/`** — Streaming query engine (#473), runs every query (#551): `plan.rs` (the operator tree of every query, or the executor's error code for it: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a magic-set head constant is `HeadArg::Const`), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; an `or` branch or a `not` body is planned as a `:where` is; a clause list with no pattern first starts from `Seed`; a constant no cell equals is `Term::Never`, a scan that reads nothing; `:as-of` resolved when the query opens (`Snapshot::tx_bound`: a counter bound when `tx_id` rises with `tx_count`, else `TxBound::Timestamp`: committed `tx_count` ranges and pending `tx_id <= t`); a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, or, under a constant attribute and entity not constant, its value (#721: per outer row the AVET ranges of the values that join-equal it and the attribute's pending facts with its key, read once per query in `IdSpace::probes`; an entity cell needs the keyword naming it, known only where the query made the entity from a keyword (rule heads, magic seeds), else the join becomes the planner's `HashJoin`); `HashJoin` otherwise, and on a relation; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `collect.rs` (`CollectSet`, #316: `[(collect-set ?e :a) ?s]` per row probes `[e :a ?v]` as an `IndexNestedLoopJoin` does and binds the values as one set, `#{}` when none, metered; `Expr::CollectSet`, parsed only as a whole binding clause), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `sort.rs` (`Sort`, #306: the `:find` columns as values, in the full order of `:order-by` — its keys, then every other `:find` column ascending, by `datalog::aggregate::row_order`/`value_order`; under a `:limit` a heap of the best `offset + limit` rows; reads its whole input, dropping the DICT lookups after each batch, metered; its rows turned back into cells only as returned), `limit.rs` (`Limit`, #306: skips `offset` rows, passes on at most `limit`, then closes its child so nothing below reads more; planned after the last step, after `Builder::finish`, and after `Sort`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare; `:distinct` adds `DistinctFind` after aggregates/windows and before sorting/pagination, keyed on final `:find` columns by aggregate-group equality, with canonical float zero/NaN output including set elements, #493), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only; bounded stack UUID hints share DICT paths, with cache insertion and charges in projection order, #530), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `meter.rs` (#549: one `Meter` per query, shared by every holder of state through a `Held` — hash join build sides, `not`/`or` tables, distinct sets, aggregate groups, window rows, rule relations and their temporaries, `IdSpace`, the set a `CollectSet` builds; each entry charged by a per-entry estimate including retained set elements and strings before it is inserted, containers grown with `try_reserve`, released on `rewind`/`close`/drop; over `OpenOptions::query_memory_limit`, or a refused allocation, is `QRY-012`; `Stream::close` drops the operator tree, keeping its counters). `mod.rs`: `Operator` (`next_batch`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` run every query on it: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it.
 
 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396)
 
@@ -216,7 +216,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**1900 tests** (1885 passing, 15 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
+**1911 tests** (1896 passing, 15 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
 See `docs/TEST_COVERAGE.md` for the full per-file breakdown.
 
 **Testing conventions** — see the Testing Conventions section below before writing any tests.

@@ -269,6 +269,8 @@ Performance envelope on the `v3` branch (format v8), measured up to 10M facts on
 | Selective 2-clause join (1 row), p50 | 38 µs | 37 µs | 37 µs |
 | Rule query with a constant (magic sets, 5–7 rows), p50 | 1.1 ms | 1.5 ms | 1.9 ms |
 
+The table above is the #551 snapshot. A later [focused UUID projection comparison](docs/BENCHMARKS.md#projected-uuid-lookup-batching-530-unreleased) measures the 1M-fact attribute scan at 262 → 136 ms p50 after batched dictionary reads (#530); the other table scales were not remeasured in that comparison.
+
 Point lookups, time travel on one entity, and joins and rule queries that a constant makes selective stay flat at every tested size. Queries that read a whole attribute (scans, aggregates, joins with nothing selective) grow linearly with the facts they read, in bounded memory: the 1.67M-row scan at 10M facts holds one batch, 7 MiB. Windows and whole transitive closures hold their rows, and `OpenOptions::query_memory_limit` stops a query that passes it with `QRY-012`. Graphs over 10M facts are not tested.
 
 File-backed databases limit string values to 4,068 bytes (`WAL-003`). In-memory databases have no limit.