From bd47f8c7aa2a64cc1f67c780b73113ad3d94c348 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 27 Oct 2026 18:50:13 +0530 Subject: [PATCH 1/2] perf(query): batch projected UUID lookups (#530) --- CHANGELOG.md | 1 + CLAUDE.md | 8 +- README.md | 2 + ROADMAP.md | 1 + docs/BENCHMARKS.md | 77 ++++ docs/TEST_COVERAGE.md | 8 +- docs/benchmarks/530-uuid-projection.jsonl | 28 ++ .../plans/2026-10-27-dict-batch.md | 39 ++ .../specs/2026-10-27-dict-batch-design.md | 72 ++++ scripts/uuid_projection_probe.rs | 74 ++++ src/query/engine/ids.rs | 21 +- src/query/engine/project.rs | 377 ++++++++++++++++++ src/query/engine/tests.rs | 27 ++ src/storage/btree.rs | 150 +++++++ src/storage/dict.rs | 110 +++++ src/storage/keys.rs | 58 ++- src/storage/mod.rs | 15 + src/storage/reader.rs | 82 ++++ 18 files changed, 1139 insertions(+), 11 deletions(-) create mode 100644 docs/benchmarks/530-uuid-projection.jsonl create mode 100644 docs/superpowers/plans/2026-10-27-dict-batch.md create mode 100644 docs/superpowers/specs/2026-10-27-dict-batch-design.md create mode 100644 scripts/uuid_projection_probe.rs diff --git a/CHANGELOG.md b/CHANGELOG.md index 74529c75d..f792ecd49 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -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 entity ids together, visiting shared B+tree paths once while keeping the same exact-key leaf lookup as scalar reads. Temporary UUID hints leave the query cache and its 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 attribute scan has 25.6% lower p50 latency (256 → 190 ms); `docs/BENCHMARKS.md` records the paired runs and reproduction. - **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 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. diff --git a/CLAUDE.md b/CLAUDE.md index 66df5fb23..caab43c16 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -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`, `get_many` (sorted exact lookups sharing child paths, #530), `MutexStorageBackend`) + - `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values; `uuids_of` shares exact-lookup tree paths for sorted id 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). +**1913 tests** (1898 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. diff --git a/README.md b/README.md index 94c4ff113..79c75151f 100644 --- a/README.md +++ b/README.md @@ -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 256 → 190 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. diff --git a/ROADMAP.md b/ROADMAP.md index fa18ba13f..52e4e0f51 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -97,6 +97,7 @@ Scope — query API: - `lag` and `lead` window functions for the previous/next row within an ordered partition (#182; v3.0.0) - Bounded sliding row frames, `:rows N preceding`, for window aggregates (#183; v3.0.0, implemented on `v3`; builds on #182) - Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) runs every query and produces rows as they are pulled: patterns, expressions and pseudo-attributes (#544), joins and `:db/valid-at` (#545), `not` and `or` (#546), aggregates and windows (#547), rules (#548), and transaction reads (#550); the executor's query path is gone (#551; done on `v3`). Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549). +- Projected UUID lookup batches share DICT tree paths (#530; implemented on `v3`), keeping temporary memory bounded to a batch and query-cache charges in projection order. - Native `:limit N`, `:order-by` and `:offset`, with a top-k `Sort` whose memory follows `N` (#306; done on `v3`, with the 10M-fact acceptance tests moved from #473; spec `docs/superpowers/specs/2026-10-24-limit-order-by-design.md`). Skipping the sort when an index already returns the rows in order is #641 (v3.next). - Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log pins its generation: checkpoints run but do not reuse its pages (#543; `API-013` deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462. - Read-only open: `OpenOptions::read_only` takes a shared lock, so several readers can hold a file at once, writes nothing to the file or its WAL (a WAL is applied in memory, a v7 file is read without migrating), and refuses writes with `API-014` (#429; Rust API done on `v3`). The bindings' `open_with_options` follows. diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index 0867864d9..1c507010f 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -2,6 +2,83 @@ This document records reproducible local benchmark snapshots. Completed release-performance history belongs in the [CHANGELOG](../CHANGELOG.md); continuous CI history is available on [Bencher](https://bencher.dev/perf/minigraf/plots). +## Projected UUID lookup batching (#530, unreleased) + +**Date**: 2026-10-27 · **Baseline**: `v3` at `80120758` · **Change**: #530. +Two rounds on an idle benchmark server, CPU and memory bound to the same NUMA +node, running baseline then change and reversing the order in round two. Builds +and tests finished before timing. Both libraries used `--profile envelope` +(opt-level 3) and `-C force-frame-pointers=yes`. Queries opened checkpointed files +read-only and warmed their caches. Profiling ran separately. The table is the mean +of each round's p50; the [raw rounds](benchmarks/530-uuid-projection.jsonl) retain +run counts, maxima and the envelope's process-wide peak RSS. + +| Workload | Baseline p50 | Change p50 | Latency delta | +|---|---:|---:|---:| +| Attribute scan, 1M facts / 166,666 rows | 255.58 ms | 190.07 ms | -25.6% | +| Point lookup, 1M facts / 1 row | 17.78 µs | 18.34 µs | +3.2% | +| Sparse entities, 1,000 rows | 2.90 ms | 2.57 ms | -11.4% | +| Random refs, 100,000 rows | 247.21 ms | 203.24 ms | -17.8% | +| Repeated refs, 100,000 rows | 87.24 ms | 75.43 ms | -13.5% | +| Two entity columns, 100,000 rows | 324.98 ms | 293.64 ms | -9.6% | +| Duplicate projected columns, 100,000 rows | 250.96 ms | 220.55 ms | -12.1% | + +The original 1M-fact envelope scan has **25.6% lower p50 latency**. Its process +peak RSS remains about 7 MiB in both versions. Point lookups remain around 18 µs; +the measured difference here is +0.56 µs. The other queries use a separate +300,000-fact fixture: 100,000 UUID entities with `:friend` pointing to +`(i * 7919 + 1) % 100000`, `:boss` to `i / 100`, and `:bucket` equal to `i % 100`. +Their expected row counts are checked on every run. Query workers use a 256 KiB +stack, including the two-column and duplicate-column cases. + +| Probe | Query | +|---|---| +| Sparse entities | `[:find ?e :where [?e :bucket 7]]` | +| Random refs | `[:find ?f :where [?e :friend ?f]]` | +| Repeated refs | `[:find ?f :where [?e :boss ?f]]` | +| Two entity columns | `[:find ?e ?f :where [?e :friend ?f]]` | +| Duplicate columns | `[:find ?f ?f :where [?e :friend ?f]]` | + +Separate user-cycle profiles of the 1M scan put scalar `DictReader::uuid_of` at +58.1% before the change and batched `DictReader::uuids_of` at 45.1% afterward. +The projection path shares B+tree descents; exact-key `leaf_get` still performs +individual leaf searches, preserving sparse-lookup behavior. Joins, collect-set +and sort/aggregate value conversions retain their existing scalar paths. + +To reproduce, build both revisions once with the envelope profile and frame +pointers. Compile the **same** [probe source](../scripts/uuid_projection_probe.rs) +against each revision's library (set `target_dir`, `probe_src` and `probe_out` +for that revision): + +```bash +rustc --edition=2024 -C opt-level=3 -C panic=abort -C force-frame-pointers=yes \ + -L dependency="$target_dir/envelope/deps" \ + --extern minigraf="$target_dir/envelope/deps/libminigraf.rlib" \ + "$probe_src" -o "$probe_out" +``` + +Use a fresh scratch directory, place the two envelope/probe executables there as +`baseline-envelope`, `changed-envelope`, `baseline-probe` and `changed-probe`, and +build the common fixtures outside the timed phase. For example, with `run_dir` +pointing to that directory and `bench_node` selecting one NUMA node: + +```bash +"$run_dir/baseline-envelope" __build "$run_dir/fixture-1m.graph" 1000000 \ + > "$run_dir/fixture-1m.json" +"$run_dir/baseline-probe" build "$run_dir/refs.graph" 100000 +numactl --cpunodebind="$bench_node" --membind="$bench_node" \ + "$run_dir/changed-envelope" __query "$run_dir/fixture-1m.graph" 2 8 60 +numactl --cpunodebind="$bench_node" --membind="$bench_node" \ + "$run_dir/changed-probe" query "$run_dir/refs.graph" \ + '(query [:find ?f :where [?e :friend ?f]])' 100000 +``` + +Run the same cases with both executable pairs, sequentially; reverse the order +for the second round. The envelope warms three runs and measures up to 200 runs +or eight seconds; the reference probe warms three runs and measures up to 200 +runs or five seconds, at least five. Remove fixtures, executables and build +outputs after retaining the reports. + ## Bounded row frames (#183, unreleased) **Date**: 2026-10-27 · **Branch**: `feat/183-row-frames` on `v3` · **Machine**: Intel Xeon E5-2696 v4, Linux 6.8, Rust 1.99.1, idle during timing. **Reproduction command**: `numactl --cpunodebind=1 --membind=1 cargo bench --bench minigraf_bench -- window_rows --sample-size 10 --warm-up-time 0.1 --measurement-time 0.2 --nresamples 1000 --noplot`. The recorded run invoked the prebuilt Criterion binary directly with its `--bench` switch after checking the machine was idle. Criterion extended the measurement time for slow cases to obtain ten samples. The committed harness uses the same in-memory facts for a default-frame and each bounded-frame comparison. Each query scans and joins the facts, sorts window input, evaluates one aggregate, and materializes the result. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index aab85dadd..aca160593 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,11 +4,11 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Passing** | 1,885 | 1,917 | +| **Passing** | 1,898 | 1,930 | | **Ignored** | 15 | 16 | -| **Total** | 1,900 | 1,933 | +| **Total** | 1,913 | 1,946 | -**Verified**: 2026-10-27 with `cargo test --quiet` (and `--features test-hooks`) on the designated bench machine. +**Verified**: 2026-10-27 with `cargo test --quiet` (and `--features test-hooks`) on the designated bench machine, followed by focused engine reruns after the final projection review fix. #183 adds bounded row-frame parser, evaluator, and integration tests; one additional plan-independence case runs with `test-hooks`, including duplicate tie keys and NaN. A sliding-sum test checks recovery after integer saturation. Grammar corpus cases cover frame spellings and rejection. A meter test checks that a zero-width min frame reserves one deque slot. An ignored bench-machine diagnostic reproduces the Criterion datasets and prints the engine meter's peak for every measured case. @@ -346,6 +346,8 @@ These tests compare the database against an independent answer rather than a sin ## Query Engine +- **Batched projected UUIDs** (#530; 13 tests): B+tree dense/sparse read-count comparison with scalar lookups, empty/invalid input, callback failure and cycles; DICT scalar agreement across chunks and sparse ids, missing/malformed requested entries and unrelated malformed values; fixed key bytes and integer-boundary ordering; committed/pending/repeated projection and duplicate columns; speculative fallback, memory refusal and scalar error order; unused entity/count queries inspected before cache release; counted scalar/speculative hidden-entity reads; duplicate-slot reclamation and bounded sorting of repeated ids; a zero-cache guard for the on-disk batch override. + - **Engine paths** (`query::engine::tests`, #473, #544) - Reaches every index choice; net-assert of pending records over committed ones; `:as-of`; valid time; long strings and reads of several batches, in memory, across checkpoints and after reopen. - Expression filters and bindings, including rebinding and failing expressions; pseudo-attribute columns; keyword/UUID/float constants against keywords, refs and UUID-named keywords. diff --git a/docs/benchmarks/530-uuid-projection.jsonl b/docs/benchmarks/530-uuid-projection.jsonl new file mode 100644 index 000000000..af950473a --- /dev/null +++ b/docs/benchmarks/530-uuid-projection.jsonl @@ -0,0 +1,28 @@ +{"max_ms": 269.36647000000005, "name": "attribute_scan", "p50_ms": 257.05593700000003, "p99_ms": 269.36647000000005, "peak_rss_kb": 7332, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 31, "round": 1, "version": "baseline", "workload": "attribute_scan_1m"} +{"max_ms": 0.035408999999999996, "name": "point_entity", "p50_ms": 0.018000000000000002, "p99_ms": 0.025644, "peak_rss_kb": 5036, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 1, "version": "baseline", "workload": "point_1m"} +{"runs": 200.0, "p50_ms": 2.905018, "max_ms": 3.485532, "rows": 1000.0, "round": 1, "version": "baseline", "workload": "sparse_entities", "stack_bytes": 262144} +{"runs": 21.0, "p50_ms": 246.781251, "max_ms": 257.312645, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "random_refs", "stack_bytes": 262144} +{"runs": 57.0, "p50_ms": 87.125893, "max_ms": 124.227527, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "repeated_refs", "stack_bytes": 262144} +{"runs": 16.0, "p50_ms": 325.925679, "max_ms": 334.407692, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "two_entity_columns", "stack_bytes": 262144} +{"runs": 20.0, "p50_ms": 250.833874, "max_ms": 261.470668, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "duplicate_columns", "stack_bytes": 262144} +{"max_ms": 201.10414400000002, "name": "attribute_scan", "p50_ms": 189.973728, "p99_ms": 201.10414400000002, "peak_rss_kb": 7336, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 42, "round": 1, "version": "changed", "workload": "attribute_scan_1m"} +{"max_ms": 0.029326, "name": "point_entity", "p50_ms": 0.01808, "p99_ms": 0.022223, "peak_rss_kb": 5196, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 1, "version": "changed", "workload": "point_1m"} +{"runs": 200.0, "p50_ms": 2.564409, "max_ms": 2.952247, "rows": 1000.0, "round": 1, "version": "changed", "workload": "sparse_entities", "stack_bytes": 262144} +{"runs": 25.0, "p50_ms": 203.333696, "max_ms": 253.693786, "rows": 100000.0, "round": 1, "version": "changed", "workload": "random_refs", "stack_bytes": 262144} +{"runs": 67.0, "p50_ms": 75.329937, "max_ms": 82.618074, "rows": 100000.0, "round": 1, "version": "changed", "workload": "repeated_refs", "stack_bytes": 262144} +{"runs": 18.0, "p50_ms": 288.149341, "max_ms": 307.092977, "rows": 100000.0, "round": 1, "version": "changed", "workload": "two_entity_columns", "stack_bytes": 262144} +{"runs": 23.0, "p50_ms": 221.045346, "max_ms": 227.356607, "rows": 100000.0, "round": 1, "version": "changed", "workload": "duplicate_columns", "stack_bytes": 262144} +{"max_ms": 243.255707, "name": "attribute_scan", "p50_ms": 190.17330900000002, "p99_ms": 243.255707, "peak_rss_kb": 7404, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 42, "round": 2, "version": "changed", "workload": "attribute_scan_1m"} +{"max_ms": 0.041279, "name": "point_entity", "p50_ms": 0.018599, "p99_ms": 0.033733, "peak_rss_kb": 5228, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 2, "version": "changed", "workload": "point_1m"} +{"runs": 200.0, "p50_ms": 2.574066, "max_ms": 3.074476, "rows": 1000.0, "round": 2, "version": "changed", "workload": "sparse_entities", "stack_bytes": 262144} +{"runs": 25.0, "p50_ms": 203.154536, "max_ms": 211.01008, "rows": 100000.0, "round": 2, "version": "changed", "workload": "random_refs", "stack_bytes": 262144} +{"runs": 66.0, "p50_ms": 75.52819, "max_ms": 82.607256, "rows": 100000.0, "round": 2, "version": "changed", "workload": "repeated_refs", "stack_bytes": 262144} +{"runs": 17.0, "p50_ms": 299.12337, "max_ms": 336.420854, "rows": 100000.0, "round": 2, "version": "changed", "workload": "two_entity_columns", "stack_bytes": 262144} +{"runs": 23.0, "p50_ms": 220.052204, "max_ms": 226.823264, "rows": 100000.0, "round": 2, "version": "changed", "workload": "duplicate_columns", "stack_bytes": 262144} +{"max_ms": 267.881656, "name": "attribute_scan", "p50_ms": 254.108311, "p99_ms": 267.881656, "peak_rss_kb": 7192, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 32, "round": 2, "version": "baseline", "workload": "attribute_scan_1m"} +{"max_ms": 0.038784, "name": "point_entity", "p50_ms": 0.017550999999999997, "p99_ms": 0.033002000000000004, "peak_rss_kb": 5080, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 2, "version": "baseline", "workload": "point_1m"} +{"runs": 200.0, "p50_ms": 2.893398, "max_ms": 3.416504, "rows": 1000.0, "round": 2, "version": "baseline", "workload": "sparse_entities", "stack_bytes": 262144} +{"runs": 21.0, "p50_ms": 247.645778, "max_ms": 254.405355, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "random_refs", "stack_bytes": 262144} +{"runs": 57.0, "p50_ms": 87.357368, "max_ms": 94.99944, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "repeated_refs", "stack_bytes": 262144} +{"runs": 16.0, "p50_ms": 324.02794, "max_ms": 332.723497, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "two_entity_columns", "stack_bytes": 262144} +{"runs": 20.0, "p50_ms": 251.088229, "max_ms": 259.18302, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "duplicate_columns", "stack_bytes": 262144} diff --git a/docs/superpowers/plans/2026-10-27-dict-batch.md b/docs/superpowers/plans/2026-10-27-dict-batch.md new file mode 100644 index 000000000..c1b73e452 --- /dev/null +++ b/docs/superpowers/plans/2026-10-27-dict-batch.md @@ -0,0 +1,39 @@ +# #530 implementation plan + +Spec: `../specs/2026-10-27-dict-batch-design.md`. Claude approved the spec and plan +on 2026-10-27 before implementation. Base: `80120758`, branch `perf/530-dict-batch`. + +1. Profile the current 1M-fact attribute scan on the idle benchmark server, envelope profile + and frame pointers. Keep a baseline executable and identical fixtures. +2. Create the ignored `.worktrees/530-dict-batch` worktree from `origin/v3`. +3. Add B+tree batch correctness/read-count regressions. Establish failure using + scalar fallback, then implement child-grouped descent with scalar `leaf_get`. + Observed: the dense read-count assertion failed with scalar lookup; all three + B+tree regressions then passed with grouped descent. +4. Add fixed DICT key and UUID batch tests; implement bounded key encoding, + `DictReader::uuids_of`, the default `KeySource` method and on-disk override. +5. Add projection regressions. Observe that mixed-id and fallback tests fail + before batching; implement bounded stack hints, scalar-order insertion and + fallback. Add the unused-entity/count guard before `end_pull`. +6. Run full default and `test-hooks` tests, CI clippy, and formatting checks on the + bench (formatting may also run locally). Keep heavy work off the laptop. +7. Build the optimized envelope and matching probe, then alternate baseline and + change timings on an idle machine. Check sparse/random/repeated projections, + a 256 KiB worker stack and point reads. Profile separately from timing. +8. Synchronize changelog, benchmark evidence, roadmap, architecture notes and + test counts; cross-check README and docs-site claims. Do not bump versions. +9. Get Claude's final review, address findings, and verify affected work before + opening the `v3` PR. Save logs locally, then remove every task-owned bench + fixture, executable, target and scratch directory. + +Implementation review follow-up: compact duplicate hint cells before enforcing +the distinct-id cap (regression observed failing, then passing); count both scalar +and speculative reads for hidden entity cells; test every integer byte boundary; +guard the on-disk override with a zero-cache read-count test. Fsync-heavy broad suites run sequentially after contention; timing runs are +pinned to one NUMA node on the idle benchmark server. Incomplete interrupted runs do not count as verification. + +The final review approved the implementation conditional on remaining checks. +Its repeated-id cost note was also addressed: a sort-count regression failed +before the buffer reused its sorted prefix, then passed with all six projection +tests. Full default and test-hooks runs passed; final focused checks cover this +last local optimization. diff --git a/docs/superpowers/specs/2026-10-27-dict-batch-design.md b/docs/superpowers/specs/2026-10-27-dict-batch-design.md new file mode 100644 index 000000000..258f36aff --- /dev/null +++ b/docs/superpowers/specs/2026-10-27-dict-batch-design.md @@ -0,0 +1,72 @@ +# Batched UUID projection (#530) + +Approved after Claude spec/plan review, 2026-10-27. Targets `v3`, format v8. + +## Problem + +The streaming engine carries DICT ids until projection, but a scan returning a +different entity in every row still performs one root-to-leaf DICT lookup per +UUID. At `80120758`, the 1M-fact envelope attribute scan spends about 58% of +sampled user cycles under `DictReader::uuid_of` on the idle bench machine. + +## Design + +`Project` resolves up to 1,024 committed entity cache misses from its returned +columns as one sorted, distinct batch. Duplicate cells are compacted when the +fixed buffer fills so they do not consume its distinct-id bound. Its temporary UUID hints live on the +stack. Pending/provisional ids and existing cache hits are excluded using the +same routing predicate as scalar `IdSpace::uuid`. One distinct miss, no misses, +and in-memory queries stay on the scalar path. + +`KeySource::uuids_of` is an additive default method: strictly increasing ids, +callbacks in that order, empty input reads nothing. Its default implementation +calls scalar `uuid_of`. `OnDiskReader` overrides it using the query's same pinned +DICT root, never a newer database state. `DictReader` encodes the ids into a +bounded fixed-size key buffer, then calls `btree::get_many`. + +`get_many` groups sorted keys by each internal node's child range, visits every +required page once, and calls today's `leaf_get` for each requested key. It +retains the scalar leaf restart-point behavior rather than decoding full leaves. +Sparse keys do not cause more backend page reads than scalar lookups. Recursion +has scalar `get`'s 32-level bound. Empty and invalid input do no reads. Unsorted +or duplicate keys are the existing internal invariant violation, `INT-049`. +Missing or malformed requested UUIDs are scalar's existing `STG-036`; unrelated +UUID values are never parsed. Fixed DICT keys preserve the existing byte format, +including integer-length boundaries. + +Hints do not populate `IdSpace` or charge its meter. When each returned cell is +converted, `uuid_with_hint` uses its hint or the scalar lookup and performs the +original charge, allocation and map insertion in row/column order. A failed or +incomplete speculative read discards all hints. Scalar errors remain authoritative, +so a later bad id or budget refusal cannot displace an earlier value error. +`end_pull` still releases committed lookup maps. No fields or retained caches are +added to the stream, reader or id space. Stack buffers are bounded independently +of database size; the heap memory meter continues counting retained query state. + +## Boundaries and philosophy + +The change optimizes projected entity/ref cells. Joins, collect-set, sorting and +aggregate value conversions retain their existing lookup behavior. It adds no +configuration, dependencies, file-format changes or release bump. Sharing exact +lookups while preserving scalar behavior follows the embedded, portable, +reliability-first design. It does not introduce a cache that grows with a query's +whole answer. + +## Acceptance + +- Dense lookup batches read shared tree paths once; sparse batches read no more + pages than scalar; empty/invalid inputs, missing keys, callbacks and cycles are + covered by deterministic tests with a disabled page cache. +- Requested UUIDs match scalar over sparse and multi-chunk subsets; unrelated + malformed values do not fail the batch; fixed encodings keep byte order. +- Projection batches committed ids even when pending/provisional ids share a + batch; repeated refs, duplicate columns, row order, fallback, memory charging + and earlier scalar errors remain correct. +- A scan which does not project entities, including a count, performs no entity + conversion before cache release. Existing multi-batch and generation-pin tests + continue to pass. +- Default and `test-hooks` suites and CI clippy run on the bench. Idle sequential + A/B measurements pinned to one NUMA node cover the original 1M scan, point reads, sparse entities and + random/repeated ref projections; profiles and timings run separately. +- Claude reviews the implementation before a PR targeting `v3`. Bench scratch + files are removed after retaining local verification evidence. diff --git a/scripts/uuid_projection_probe.rs b/scripts/uuid_projection_probe.rs new file mode 100644 index 000000000..60c061a02 --- /dev/null +++ b/scripts/uuid_projection_probe.rs @@ -0,0 +1,74 @@ +//! Reproducible UUID projection fixture/query probe for #530. +//! +//! Compile against either comparison library with rustc (docs/BENCHMARKS.md). +//! Usage: probe build +//! probe query '' +//! Query timings exclude file open and thread creation; the worker stack is 256 KiB. + +use minigraf::{Minigraf, OpenOptions}; +use std::time::{Duration, Instant}; + +fn uuid(i: usize) -> String { + format!("00000000-0000-0000-0000-{i:012x}") +} +fn main() { + let args: Vec<_> = std::env::args().collect(); + if args[1] == "build" { + let n: usize = args[3].parse().unwrap(); + assert!( + !std::path::Path::new(&args[2]).exists(), + "fixture must be built from scratch" + ); + let db = Minigraf::open(&args[2]).unwrap(); + for start in (0..n).step_by(1000) { + let mut command = String::from("(transact ["); + for i in start..(start + 1000).min(n) { + command.push_str(&format!("[#uuid \"{}\" :friend #uuid \"{}\"] [#uuid \"{}\" :boss #uuid \"{}\"] [#uuid \"{}\" :bucket {}]", uuid(i), uuid((i*7919+1)%n), uuid(i), uuid(i/100), uuid(i), i%100)); + } + command.push_str("])"); + db.execute(&command).unwrap(); + } + db.checkpoint().unwrap(); + return; + } + std::thread::Builder::new() + .stack_size(256 * 1024) + .spawn(move || { + let db = OpenOptions::new() + .read_only(true) + .path(&args[2]) + .open() + .unwrap(); + let expected: usize = args[4].parse().unwrap(); + let drain = || { + let mut cursor = db.query(&args[3]).unwrap(); + let mut count = 0; + while let Some(batch) = cursor.next_batch(1000).unwrap() { + count += batch.len(); + } + assert_eq!(count, expected); + }; + for _ in 0..3 { + drain(); + } + let start = Instant::now(); + let mut times = Vec::new(); + while times.len() < 200 && (times.len() < 5 || start.elapsed() < Duration::from_secs(5)) + { + let t = Instant::now(); + drain(); + times.push(t.elapsed().as_secs_f64() * 1000.0); + } + times.sort_by(f64::total_cmp); + println!( + "runs={},p50_ms={:.6},max_ms={:.6},rows={}", + times.len(), + times[times.len() / 2], + times.last().unwrap(), + expected + ); + }) + .unwrap() + .join() + .unwrap(); +} diff --git a/src/query/engine/ids.rs b/src/query/engine/ids.rs index 37442cb3e..2a256a6be 100644 --- a/src/query/engine/ids.rs +++ b/src/query/engine/ids.rs @@ -183,6 +183,22 @@ impl IdSpace { /// The entity with id `eid`. pub(crate) fn uuid(&mut self, keys: Option<&dyn KeySource>, eid: u64) -> Result { + self.uuid_with_hint(keys, eid, None) + } + + /// Exactly the committed misses scalar `uuid` would send to DICT. + pub(crate) fn needs_uuid(&self, eid: u64) -> bool { + eid < self.dict_eids && !self.dict.uuid_by_eid.contains_key(&eid) + } + + /// A successful speculative read may supply the UUID, but charging and + /// insertion still happen only when the caller projects this cell. + pub(crate) fn uuid_with_hint( + &mut self, + keys: Option<&dyn KeySource>, + eid: u64, + hint: Option, + ) -> Result { let maps = self.maps(eid >= self.dict_eids); if let Some(u) = maps.uuid_by_eid.get(&eid) { return Ok(*u); @@ -193,7 +209,10 @@ impl IdSpace { format!("query engine: unknown entity id {eid}") )); }; - let u = k.uuid_of(eid)?; + let u = match hint { + Some(u) => u, + None => k.uuid_of(eid)?, + }; self.charge(false, EID_ENTRY, grow_eid)?; self.dict.uuid_by_eid.insert(eid, u); self.dict.eid_by_uuid.insert(u, eid); diff --git a/src/query/engine/project.rs b/src/query/engine/project.rs index 8eaf79f4f..e0738a391 100644 --- a/src/query/engine/project.rs +++ b/src/query/engine/project.rs @@ -3,20 +3,32 @@ //! Only rows that are returned are converted, so a query reads ids until //! the end (#530). +use super::BATCH_ROWS; use super::Ctx; use super::batch::Batch; use super::cell::{Cell, Scalar}; use crate::graph::types::{Value, ValueSet}; use anyhow::Result; +#[cfg(test)] +thread_local! { + static HINT_SORTS: std::cell::Cell = const { std::cell::Cell::new(0) }; +} + /// The rows of `batch`, with the cells of the slots `find` as values. pub(crate) fn project(batch: &Batch, find: &[usize], ctx: &mut Ctx<'_>) -> Result>> { + let hints = Uuids::read(batch, find, ctx); let mut rows = Vec::with_capacity(batch.len); for i in 0..batch.len { let mut row = Vec::with_capacity(find.len()); for &slot in find { let cell = batch.cols.get(slot).and_then(|c| c.get(i)); row.push(match cell { + Some(Cell::Eid(e)) => Value::Ref(ctx.ids.uuid_with_hint( + ctx.keys, + *e, + hints.as_ref().and_then(|h| h.get(*e)), + )?), Some(cell) => value(cell, ctx)?, None => Value::Null, }); @@ -26,6 +38,112 @@ pub(crate) fn project(batch: &Batch, find: &[usize], ctx: &mut Ctx<'_>) -> Resul Ok(rows) } +/// Bounded, unmetered stack hints: they never change query state. Populate +/// IdSpace only in projection order, so earlier errors and memory charges +/// remain scalar's. Failed speculative reads discard every partial hint. +struct Uuids { + ids: [u64; BATCH_ROWS], + values: [crate::graph::types::EntityId; BATCH_ROWS], + len: usize, +} + +impl Uuids { + fn read(batch: &Batch, find: &[usize], ctx: &Ctx<'_>) -> Option { + let keys = ctx.keys?; + let candidates = || { + (0..batch.len).flat_map(|row| { + find.iter().filter_map(move |&slot| { + match batch.cols.get(slot).and_then(|c| c.get(row)) { + Some(Cell::Eid(e)) if ctx.ids.needs_uuid(*e) => Some(*e), + _ => None, + } + }) + }) + }; + let mut probe = candidates(); + let first = probe.next()?; + if !probe.any(|e| e != first) { + return None; + } + let mut hints = Self { + ids: [0; BATCH_ROWS], + values: [crate::graph::types::EntityId::nil(); BATCH_ROWS], + len: 0, + }; + let mut sorted = 0; + for eid in candidates() { + if hints.ids.get(..sorted)?.binary_search(&eid).is_ok() { + continue; + } + if hints.len == BATCH_ROWS { + hints.compact()?; + sorted = hints.len; + if hints.len == BATCH_ROWS { + break; + } + if hints.ids.get(..sorted)?.binary_search(&eid).is_ok() { + continue; + } + } + *hints.ids.get_mut(hints.len)? = eid; + hints.len += 1; + } + hints.compact()?; + let count = hints.len; + if count < 2 { + return None; + } + let ids = hints.ids.get(..count)?; + let mut expected = ids.iter(); + let mut output = hints.values.iter_mut(); + let mut read = 0; + keys.uuids_of(ids, &mut |eid, uuid| { + let wanted = expected.next(); + debug_assert_eq!(wanted, Some(&eid), "UUID batch changed requested order"); + if wanted != Some(&eid) { + return Err(crate::error::err_coded!( + crate::error::ErrorCode::Int049, + "UUID batch returned a different id" + )); + } + let dst = output.next().ok_or_else(|| { + crate::error::err_coded!(crate::error::ErrorCode::Int049, "too many UUID hints") + })?; + *dst = uuid; + read += 1; + Ok(()) + }) + .ok()?; + debug_assert_eq!(read, count, "incomplete UUID batch"); + (read == count).then_some(hints) + } + + /// Reclaim duplicate slots before deciding the distinct-id bound is full. + fn compact(&mut self) -> Option<()> { + let ids = self.ids.get_mut(..self.len)?; + #[cfg(test)] + HINT_SORTS.with(|n| n.set(n.get() + 1)); + ids.sort_unstable(); + let mut count = 0; + let mut previous = None; + for i in 0..ids.len() { + let eid = *ids.get(i)?; + if previous != Some(eid) { + *ids.get_mut(count)? = eid; + count += 1; + previous = Some(eid); + } + } + self.len = count; + Some(()) + } + + fn get(&self, eid: u64) -> Option { + let i = self.ids.get(..self.len)?.binary_search(&eid).ok()?; + self.values.get(i).copied() + } +} + /// The value of `cell`. pub(crate) fn value(cell: &Cell, ctx: &mut Ctx<'_>) -> Result { Ok(match cell { @@ -48,3 +166,262 @@ pub(crate) fn value(cell: &Cell, ctx: &mut Ctx<'_>) -> Result { }, }) } + +#[cfg(test)] +mod tests { + use super::*; + use crate::error::{ErrorCode, err_coded}; + use crate::graph::storage::FactStorage; + use crate::query::datalog::functions::FunctionRegistry; + use crate::query::engine::ids::IdSpace; + use crate::query::engine::meter::Meter; + use crate::storage::keys::{Index, KeyFact, ValueRef}; + use crate::storage::{KeySource, TxBound, TxOrder}; + use std::sync::atomic::{AtomicUsize, Ordering}; + + struct Keys { + bulk: AtomicUsize, + scalar: AtomicUsize, + fail_bulk: bool, + limit: u64, + } + + impl Keys { + fn new(fail_bulk: bool) -> Self { + Self { + bulk: AtomicUsize::new(0), + scalar: AtomicUsize::new(0), + fail_bulk, + limit: 3, + } + } + } + + // The unused storage operations cannot affect a projection-only test. + impl KeySource for Keys { + fn next_ids(&self) -> (u64, u32) { + (self.limit, 1) + } + fn eid_of(&self, _: &uuid::Uuid) -> Result> { + Ok(None) + } + fn uuid_of(&self, eid: u64) -> Result { + self.scalar.fetch_add(1, Ordering::Relaxed); + assert!(eid < self.limit, "provisional ids must not read DICT"); + Ok(uuid::Uuid::from_u128(u128::from(eid))) + } + fn uuids_of( + &self, + eids: &[u64], + visit: &mut dyn FnMut(u64, uuid::Uuid) -> Result<()>, + ) -> Result<()> { + self.bulk.fetch_add(1, Ordering::Relaxed); + for &e in eids { + assert!(e < self.limit, "only committed misses are batched"); + visit(e, uuid::Uuid::from_u128(u128::from(e)))?; + if self.fail_bulk { + anyhow::bail!("speculative failure after one hint"); + } + } + Ok(()) + } + fn iid_of(&self, _: &str) -> Result> { + panic!("unused") + } + fn ident_of(&self, _: u32) -> Result { + panic!("unused") + } + fn long_value(&self, _: ValueRef) -> Result { + Err(err_coded!(ErrorCode::Stg036, "first scalar error")) + } + fn long_value_ref(&self, _: &str) -> Result> { + panic!("unused") + } + fn long_bytes(&self, _: ValueRef) -> Result> { + panic!("unused") + } + fn long_bytes_ref(&self, _: &[u8]) -> Result> { + panic!("unused") + } + fn tx_id_of(&self, _: u64) -> Result { + panic!("unused") + } + fn tx_order(&self) -> Result { + panic!("unused") + } + fn last_tx_at(&self, _: u64) -> Result { + panic!("unused") + } + fn tx_runs(&self, _: u64, _: &mut Vec<(u64, u64)>) -> Result<()> { + panic!("unused") + } + fn live_keys( + &self, + _: Index, + _: &[u8], + _: Option<&[u8]>, + _: &TxBound, + _: usize, + _: &mut Vec, + ) -> Result>> { + panic!("unused") + } + } + + fn project_with( + keys: &Keys, + batch: &Batch, + find: &[usize], + limit: usize, + ) -> Result>> { + let snapshot = FactStorage::new().snapshot().unwrap(); + let meter = Meter::new(limit); + let mut ids = IdSpace::new(Some(keys), &meter); + let functions = FunctionRegistry::with_builtins(); + let mut ctx = Ctx { + snapshot: &snapshot, + keys: Some(keys), + ids: &mut ids, + functions: &functions, + derived: None, + bound: &TxBound::All, + }; + project(batch, find, &mut ctx) + } + + #[test] + fn projection_batches_committed_ids_among_provisional_and_repeated_ids() { + let keys = Keys::new(false); + let snapshot = FactStorage::new().snapshot().unwrap(); + let meter = Meter::unlimited(); + let mut ids = IdSpace::new(Some(&keys), &meter); + let pending = uuid::Uuid::from_u128(100); + let provisional = ids.eid(None, &pending).unwrap(); + let mut batch = Batch::new(1); + for e in [2, provisional, 1, 2] { + batch.push(&mut [Some(Cell::Eid(e))]); + } + let functions = FunctionRegistry::with_builtins(); + let mut ctx = Ctx { + snapshot: &snapshot, + keys: Some(&keys), + ids: &mut ids, + functions: &functions, + derived: None, + bound: &TxBound::All, + }; + let rows = project(&batch, &[0, 0], &mut ctx).unwrap(); + let expected: Vec<_> = [ + uuid::Uuid::from_u128(2), + pending, + uuid::Uuid::from_u128(1), + uuid::Uuid::from_u128(2), + ] + .into_iter() + .map(|u| vec![Value::Ref(u); 2]) + .collect(); + assert!( + rows == expected, + "row order, duplicate columns and pending UUIDs preserved" + ); + assert_eq!(keys.bulk.load(Ordering::Relaxed), 1); + assert_eq!(keys.scalar.load(Ordering::Relaxed), 0); + assert_eq!(ids.dict_cached(), 2); + ids.end_pull(); + assert_eq!(ids.dict_cached(), 0); + } + + #[test] + fn projection_reclaims_duplicate_hint_slots() { + for find in [vec![0, 0], vec![0, 1, 0, 1]] { + let mut keys = Keys::new(false); + keys.limit = u64::try_from(BATCH_ROWS + 1).unwrap(); + let mut batch = Batch::new(2); + for i in 0..BATCH_ROWS { + let e = u64::try_from(i + 1).unwrap(); + let f = u64::try_from((i + BATCH_ROWS / 2) % BATCH_ROWS + 1).unwrap(); + batch.push(&mut [Some(Cell::Eid(e)), Some(Cell::Eid(f))]); + } + let rows = project_with(&keys, &batch, &find, usize::MAX).unwrap(); + assert_eq!(rows.len(), BATCH_ROWS); + assert_eq!(keys.bulk.load(Ordering::Relaxed), 1); + assert_eq!( + keys.scalar.load(Ordering::Relaxed), + 0, + "duplicates must not exhaust the hint buffer" + ); + } + } + + #[test] + fn repeated_ids_do_not_sort_a_nearly_full_buffer_for_each_cell() { + let mut keys = Keys::new(false); + keys.limit = u64::try_from(BATCH_ROWS).unwrap(); + let mut batch = Batch::new(2); + for i in 0..BATCH_ROWS { + let e = u64::try_from((2 * i + 1).min(BATCH_ROWS - 1)).unwrap(); + let f = u64::try_from((2 * i + 2).min(BATCH_ROWS - 1)).unwrap(); + batch.push(&mut [Some(Cell::Eid(e)), Some(Cell::Eid(f))]); + } + HINT_SORTS.with(|n| n.set(0)); + let rows = project_with(&keys, &batch, &[0, 1], usize::MAX).unwrap(); + assert_eq!(rows.len(), BATCH_ROWS); + assert_eq!(keys.scalar.load(Ordering::Relaxed), 0); + HINT_SORTS.with(|n| assert!(n.get() <= 3, "repeats should reuse the sorted prefix")); + } + + #[test] + fn unprojected_entity_cells_make_no_scalar_or_speculative_reads() { + let keys = Keys::new(false); + let mut batch = Batch::new(2); + for e in [1, 2] { + batch.push(&mut [Some(Cell::Eid(e)), Some(Cell::Val(Scalar::Int(7)))]); + } + let rows = project_with(&keys, &batch, &[1], usize::MAX).unwrap(); + assert!(rows == vec![vec![Value::Integer(7)]; 2]); + assert_eq!(keys.bulk.load(Ordering::Relaxed), 0); + assert_eq!(keys.scalar.load(Ordering::Relaxed), 0); + } + + #[test] + fn speculative_failure_falls_back_without_spending_the_query_budget() { + let keys = Keys::new(true); + let mut batch = Batch::new(1); + for e in [2, 1] { + batch.push(&mut [Some(Cell::Eid(e))]); + } + let rows = project_with(&keys, &batch, &[0], usize::MAX).unwrap(); + assert_eq!(rows.len(), 2); + assert_eq!(keys.bulk.load(Ordering::Relaxed), 1); + assert_eq!( + keys.scalar.load(Ordering::Relaxed), + 2, + "discard every partial hint" + ); + let error = project_with(&Keys::new(false), &batch, &[0], 0).unwrap_err(); + assert_eq!(crate::MinigrafError::from(error).code(), "QRY-012"); + } + + #[test] + fn hints_preserve_scalar_error_order_before_id_charges() { + for fail_bulk in [false, true] { + let keys = Keys::new(fail_bulk); + let mut batch = Batch::new(2); + for e in [2, 1] { + batch.push(&mut [ + Some(Cell::Val(Scalar::Long(ValueRef { page: 42, slot: 0 }))), + Some(Cell::Eid(e)), + ]); + } + let error = project_with(&keys, &batch, &[0, 1], 0).unwrap_err(); + let error = crate::MinigrafError::from(error); + assert_eq!( + error.code(), + "STG-036", + "earlier long-value error beats later memory refusal" + ); + assert!(error.to_string().contains("first scalar error")); + assert_eq!(keys.scalar.load(Ordering::Relaxed), 0); + } + } +} diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 7785b64b7..7c0f35dbc 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -834,6 +834,33 @@ fn dict_cache_is_dropped_after_each_pull() { assert_eq!(rows, 3002); } +/// Inspect before end_pull, so clearing the cache cannot hide eager lookups. +#[test] +fn unprojected_entities_are_not_resolved() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("unprojected.graph")).unwrap(); + let facts: String = (0..3000).map(|i| format!("[:p{i} :age {i}]")).collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + db.checkpoint().unwrap(); + for query in [ + "(query [:find ?a :where [?e :age ?a]])", + "(query [:find (count ?e) :where [?e :age ?a]])", + ] { + let mut cursor = db.query(query).unwrap(); + let stream = cursor.stream_mut().unwrap(); + let mut count = 0; + while let Some(rows) = stream.pull().unwrap() { + count += rows.len(); + assert_eq!( + stream.ids.dict_cached(), + 0, + "no entity conversion before cache release" + ); + } + assert!(count > 0); + } +} + /// A stream that ends in a `Window` keeps its DICT lookups until it ends: /// the window looked up every row's ids in its first pull, and the rows it /// returns later read them from the cache (#547). diff --git a/src/storage/btree.rs b/src/storage/btree.rs index 2df9f55f7..1fcc05272 100644 --- a/src/storage/btree.rs +++ b/src/storage/btree.rs @@ -862,6 +862,71 @@ pub fn get( ) } +/// Exact lookups of sorted, distinct keys, visited in key order. +pub(crate) fn get_many>( + root: u64, + keys: &[K], + backend: &dyn StorageBackend, + cache: &PageCache, + visit: &mut impl FnMut(&K, Option>) -> Result<()>, +) -> Result<()> { + if keys + .iter() + .zip(keys.iter().skip(1)) + .any(|(a, b)| a.as_ref() >= b.as_ref()) + { + bail_coded!(ErrorCode::Int049, "lookup keys not sorted and distinct"); + } + get_many_at(root, keys, backend, cache, visit, 0) +} + +fn get_many_at>( + root: u64, + mut keys: &[K], + backend: &dyn StorageBackend, + cache: &PageCache, + visit: &mut impl FnMut(&K, Option>) -> Result<()>, + depth: usize, +) -> Result<()> { + if keys.is_empty() { + return Ok(()); + } + if depth == MAX_TREE_DEPTH { + bail_coded!( + ErrorCode::Int049, + format!("tree deeper than {MAX_TREE_DEPTH} below page_id={root}") + ); + } + let page = cache.get_or_load(root, backend)?; + match page.first().copied() { + Some(PAGE_TYPE_LEAF) => { + for key in keys { + visit(key, leaf_get(&page, key.as_ref())?)?; + } + } + Some(PAGE_TYPE_INTERNAL) => { + let node = Internal::new(&page)?; + while let Some(first) = keys.first() { + let child = node.route(first.as_ref(), 0)?; + let end = if child == node.count() { + keys.len() + } else { + let sep = node.sep(child)?; + keys.partition_point(|k| k.as_ref() < sep) + }; + if end == 0 { + bail_coded!(ErrorCode::Int049, "lookup child does not cover its key"); + } + let (group, rest) = keys.split_at(end); + get_many_at(node.child(child)?, group, backend, cache, visit, depth + 1)?; + keys = rest; + } + } + _ => bail_coded!(ErrorCode::Stg013, root), + } + Ok(()) +} + /// Every entry of the tree, in key order. #[cfg(test)] pub fn stream_all_entries( @@ -1427,6 +1492,91 @@ mod tests { } } + #[test] + fn get_many_shares_paths_without_reading_unrequested_leaves() { + let mut backend = CountingBackend { + inner: MemoryBackend::new(), + reads: std::sync::atomic::AtomicU64::new(0), + }; + let cache = PageCache::new(0); + let (root, _) = build_at(even_entries(20_000), &mut backend, &cache, 2); + for (step, dense) in [(1, true), (137, false)] { + let requested: Vec<_> = (0..1024).map(|i| key_for(i * step)).collect(); + backend.reset(); + let expected: Vec<_> = requested + .iter() + .map(|k| get(root, k, &backend, &cache).unwrap()) + .collect(); + let scalar_reads = backend.reads(); + backend.reset(); + let mut actual = Vec::new(); + get_many(root, &requested, &backend, &cache, &mut |_, v| { + actual.push(v); + Ok(()) + }) + .unwrap(); + assert_eq!(actual, expected, "same hits and misses in key order"); + assert!(backend.reads() <= scalar_reads, "sparse reads do not grow"); + if dense { + assert!( + backend.reads() < scalar_reads / 4, + "dense reads share paths" + ); + } + } + } + + #[test] + fn get_many_checks_input_and_stops_on_callback_error() { + let mut backend = CountingBackend { + inner: MemoryBackend::new(), + reads: std::sync::atomic::AtomicU64::new(0), + }; + let cache = PageCache::new(0); + let (root, _) = build_at(even_entries(100), &mut backend, &cache, 2); + backend.reset(); + get_many::>(root, &[], &backend, &cache, &mut |_, _| { + panic!("empty input must not visit"); + }) + .unwrap(); + assert_eq!(backend.reads(), 0); + for requested in [vec![key_for(2), key_for(1)], vec![key_for(1); 2]] { + let error = get_many(root, &requested, &backend, &cache, &mut |_, _| { + panic!("invalid input must not visit"); + }) + .unwrap_err(); + assert_eq!(crate::MinigrafError::from(error).code(), "INT-049"); + } + assert_eq!(backend.reads(), 0, "invalid input must not read"); + let mut visits = 0; + assert!( + get_many( + root, + &[key_for(0), key_for(2)], + &backend, + &cache, + &mut |_, _| { + visits += 1; + anyhow::bail!("visitor failed") + } + ) + .is_err() + ); + assert_eq!(visits, 1); + } + + #[test] + fn get_many_refuses_a_cycle() { + let (mut backend, cache, root, _) = multi_leaf_tree(); + let count = Internal::new(&cache.get_or_load(root, &backend).unwrap()) + .unwrap() + .count(); + redirect_child(&mut backend, &cache, root, count, root); + let error = + get_many(root, &[vec![255; 32]], &backend, &cache, &mut |_, _| Ok(())).unwrap_err(); + assert_eq!(crate::MinigrafError::from(error).code(), "INT-049"); + } + /// Entities `0, 2, 4, ...` so every odd entity is absent. fn even_entries(n: u64) -> Vec { (0..n).map(|i| entry(i * 2, 1)).collect() diff --git a/src/storage/dict.rs b/src/storage/dict.rs index 323ee968b..3974b96f0 100644 --- a/src/storage/dict.rs +++ b/src/storage/dict.rs @@ -29,6 +29,13 @@ use uuid::Uuid; /// Entries a [`SharedDictCache`] map holds before it is cleared. const SHARED_CACHE_LIMIT: usize = 65_536; +pub(crate) fn check_eids(eids: &[u64]) -> Result<()> { + if eids.iter().zip(eids.iter().skip(1)).any(|(a, b)| a >= b) { + bail_coded!(ErrorCode::Int049, "entity ids not sorted and distinct"); + } + Ok(()) +} + /// Ident and transaction lookups shared by every read of one committed meta. /// They never change once committed, and there are few of them compared with /// entities, so they are cached across reads; each map is cleared when it @@ -175,6 +182,53 @@ impl<'a> DictReader<'a> { Ok(u) } + /// Resolve only the requested ids, sharing each visited DICT tree path. + /// Neither this reader's maps nor a query's metered maps are populated. + pub(crate) fn uuids_of( + &self, + eids: &[u64], + visit: &mut dyn FnMut(u64, Uuid) -> Result<()>, + ) -> Result<()> { + check_eids(eids)?; + if eids.is_empty() { + return Ok(()); + } + if self.root == 0 { + bail_coded!( + ErrorCode::Stg036, + format!("entity id {}", eids.first().copied().unwrap_or(0)) + ); + } + // Stack storage bounds temporary memory even for callers larger than + // one engine batch. No per-key allocations or ephemeral UUID map. + let mut encoded = [keys::EidKey::default(); 1024]; + for chunk in eids.chunks(encoded.len()) { + for (dst, &eid) in encoded.iter_mut().zip(chunk) { + *dst = keys::EidKey::new(eid); + } + let mut ids = chunk.iter(); + btree::get_many( + self.root, + encoded.get(..chunk.len()).unwrap_or(&[]), + self.backend, + self.cache, + &mut |_, value| { + let eid = ids + .next() + .copied() + .ok_or_else(|| err_coded!(ErrorCode::Int049, "too many UUID lookups"))?; + let value = value + .ok_or_else(|| err_coded!(ErrorCode::Stg036, format!("entity id {eid}")))?; + let uuid = Uuid::from_slice(&value).map_err(|_| { + err_coded!(ErrorCode::Stg036, format!("entity id {eid}: bad UUID")) + })?; + visit(eid, uuid) + }, + )?; + } + Ok(()) + } + pub fn name_of(&mut self, iid: u32) -> Result { if let Some(n) = self.names.get(&iid) { return Ok(n.clone()); @@ -579,6 +633,62 @@ mod tests { } } + #[test] + fn uuid_batches_match_scalar_and_only_decode_requested_values() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(0); + let mut entries: Vec<_> = (1..=2500u64) + .map(|e| { + ( + keys::dict_eid_key(e), + Uuid::from_u128(u128::from(e)).as_bytes().to_vec(), + ) + }) + .collect(); + // A damaged value must only fail when it is actually requested. + entries.push((keys::dict_eid_key(2501), vec![0])); + let mut alloc = PageAllocator::new(Vec::new(), 2, 1); + let root = btree::build_btree(entries, &mut backend, &cache, &mut alloc).unwrap(); + let dict = DictReader::new(root, &backend, &cache); + for requested in [ + Vec::new(), + (1..=2500).collect(), + vec![1, 255, 256, 2048, 2500], + ] { + let mut actual = Vec::new(); + dict.uuids_of(&requested, &mut |e, u| { + actual.push((e, u)); + Ok(()) + }) + .unwrap(); + let mut scalar = DictReader::new(root, &backend, &cache); + let expected: Vec<_> = requested + .iter() + .map(|&e| (e, scalar.uuid_of(e).unwrap())) + .collect(); + assert!(actual == expected, "same UUIDs in requested order"); + } + for requested in [vec![2501], vec![3000], vec![2, 1], vec![1, 1]] { + let error = dict.uuids_of(&requested, &mut |_, _| Ok(())).unwrap_err(); + let code = crate::MinigrafError::from(error).code(); + assert_eq!( + code, + if requested.first() == Some(&1) || requested.first() == Some(&2) { + "INT-049" + } else { + "STG-036" + } + ); + } + let empty = DictReader::new(0, &backend, &cache); + empty.uuids_of(&[], &mut |_, _| panic!("no ids")).unwrap(); + assert_eq!( + crate::MinigrafError::from(empty.uuids_of(&[1], &mut |_, _| Ok(())).unwrap_err()) + .code(), + "STG-036" + ); + } + /// Encode `facts` on top of the dictionary at `root`, write the new DICT /// tree, and return `(new_root, encoded)`. fn checkpoint( diff --git a/src/storage/keys.rs b/src/storage/keys.rs index 483adbe07..0aed5f09d 100644 --- a/src/storage/keys.rs +++ b/src/storage/keys.rs @@ -822,9 +822,39 @@ pub fn dict_uuid_key(uuid: &Uuid) -> Vec { } pub fn dict_eid_key(eid: u64) -> Vec { - let mut k = vec![DICT_EID_TO_UUID]; - put_uint(&mut k, eid); - k + EidKey::new(eid).as_ref().to_vec() +} + +/// A DICT entity key without an allocation, for bounded lookup batches. +#[derive(Clone, Copy, Default)] +pub(crate) struct EidKey { + bytes: [u8; 10], + len: u8, +} + +impl EidKey { + pub(crate) fn new(eid: u64) -> Self { + let (bytes, skip) = magnitude_bytes(eid); + let tail = bytes.get(skip..).unwrap_or(&[]); + let n = u8::try_from(tail.len()).unwrap_or(8); + let mut key = Self { + bytes: [0; 10], + len: 2 + n, + }; + for (dst, src) in key.bytes.iter_mut().zip([DICT_EID_TO_UUID, INT_ZERO + n]) { + *dst = src; + } + for (dst, src) in key.bytes.iter_mut().skip(2).zip(tail) { + *dst = *src; + } + key + } +} + +impl AsRef<[u8]> for EidKey { + fn as_ref(&self) -> &[u8] { + self.bytes.get(..usize::from(self.len)).unwrap_or(&[]) + } } pub fn dict_ident_key(ident: &str) -> Vec { @@ -1482,6 +1512,28 @@ mod tests { ); } + #[test] + fn fixed_eid_keys_match_dictionary_encoding_and_order() { + let mut ids = vec![0, 1]; + for bytes in 1..8 { + let boundary = 1u64 << (bytes * 8); + ids.extend([boundary - 1, boundary]); + } + ids.push(u64::MAX); + let mut previous = Vec::new(); + for eid in ids { + let fixed = EidKey::new(eid); + let mut expected = vec![DICT_EID_TO_UUID]; + put_uint(&mut expected, eid); + assert_eq!(fixed.as_ref(), expected); + assert!( + previous.as_slice() < fixed.as_ref(), + "ids retain byte order" + ); + previous = fixed.as_ref().to_vec(); + } + } + #[test] fn malformed_keys_are_int_049() { for bad in [&[][..], &[0x30][..], &[0x15][..], &[TAG_STRING, b'a'][..]] { diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 377e5a7d0..e97329763 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -516,6 +516,21 @@ pub trait KeySource: Send + Sync { fn iid_of(&self, ident: &str) -> Result>; /// The entity with id `eid`. fn uuid_of(&self, eid: u64) -> Result; + /// Visit the UUIDs of strictly increasing, distinct committed entity ids. + /// Uses this reader's pinned generation, just as [`Self::uuid_of`] does. + /// An empty slice reads nothing; invalid ordering is `INT-049`. + /// The default performs scalar lookups; on-disk readers share tree paths. + fn uuids_of( + &self, + eids: &[u64], + visit: &mut dyn FnMut(u64, crate::graph::types::EntityId) -> Result<()>, + ) -> Result<()> { + dict::check_eids(eids)?; + for &eid in eids { + visit(eid, self.uuid_of(eid)?)?; + } + Ok(()) + } /// The ident with id `iid`. fn ident_of(&self, iid: u32) -> Result; /// The long string stored at `vref`. diff --git a/src/storage/reader.rs b/src/storage/reader.rs index 5e096a307..467486bad 100644 --- a/src/storage/reader.rs +++ b/src/storage/reader.rs @@ -314,6 +314,14 @@ impl KeySource for OnDiskReader { self.dict().uuid_of(eid) } + fn uuids_of( + &self, + eids: &[u64], + visit: &mut dyn FnMut(u64, EntityId) -> Result<()>, + ) -> Result<()> { + self.dict().uuids_of(eids, visit) + } + fn ident_of(&self, iid: u32) -> Result { self.dict().name_of(iid) } @@ -579,3 +587,77 @@ pub fn all_entries_as_facts( .map(|(k, _)| dict.fact(&KeyFact::decode(index, k)?)) .collect() } + +#[cfg(test)] +mod uuid_batch_tests { + use super::*; + use crate::storage::backend::MemoryBackend; + use crate::storage::page::PageAllocator; + use std::sync::atomic::{AtomicUsize, Ordering}; + + struct CountReads { + inner: MemoryBackend, + reads: AtomicUsize, + } + + impl StorageBackend for CountReads { + fn write_page(&mut self, id: u64, bytes: &[u8]) -> Result<()> { + self.inner.write_page(id, bytes) + } + fn read_page(&self, id: u64) -> Result> { + self.reads.fetch_add(1, Ordering::Relaxed); + self.inner.read_page(id) + } + fn sync(&mut self) -> Result<()> { + self.inner.sync() + } + fn page_count(&self) -> Result { + self.inner.page_count() + } + fn close(&mut self) -> Result<()> { + self.inner.close() + } + fn backend_name(&self) -> &'static str { + "counted memory" + } + } + + #[test] + fn on_disk_uuid_override_shares_paths() { + let mut backend = CountReads { + inner: MemoryBackend::new(), + reads: AtomicUsize::new(0), + }; + let cache = Arc::new(PageCache::new(0)); + let entries = (1..=2048u64) + .map(|e| { + ( + keys::dict_eid_key(e), + EntityId::from_u128(u128::from(e)).as_bytes().to_vec(), + ) + }) + .collect(); + let mut alloc = PageAllocator::new(Vec::new(), 2, 1); + let mut meta = MetaPage::empty(1); + meta.dict_root = + crate::storage::btree::build_btree(entries, &mut backend, &cache, &mut alloc).unwrap(); + meta.next_eid = 2049; + let backend = Arc::new(Mutex::new(backend)); + let reader = OnDiskReader::new(backend.clone(), cache, &meta); + let requested: Vec<_> = (1..=2048).collect(); + backend.lock().unwrap().reads.store(0, Ordering::Relaxed); + let mut seen = 0; + reader + .uuids_of(&requested, &mut |e, u| { + assert!(u == EntityId::from_u128(u128::from(e)), "same UUID"); + seen += 1; + Ok(()) + }) + .unwrap(); + assert_eq!(seen, requested.len()); + assert!( + backend.lock().unwrap().reads.load(Ordering::Relaxed) < requested.len() / 4, + "on-disk override must share paths rather than use the scalar default" + ); + } +} From c08eaade52563f5ff7003298ea6c6dadca46e294 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 27 Oct 2026 20:18:58 +0530 Subject: [PATCH 2/2] perf(query): reuse leaf cursors for dense UUID batches --- CHANGELOG.md | 2 +- CLAUDE.md | 6 +- README.md | 2 +- ROADMAP.md | 2 +- docs/BENCHMARKS.md | 86 ++++++--- docs/TEST_COVERAGE.md | 8 +- docs/benchmarks/530-uuid-projection.jsonl | 84 ++++++--- .../plans/2026-10-27-dict-batch.md | 78 +++++---- .../specs/2026-10-27-dict-batch-design.md | 112 ++++++------ scripts/uuid_projection_probe.rs | 68 +++++++- src/query/engine/project.rs | 88 +++++----- src/storage/btree.rs | 164 ++---------------- src/storage/dict.rs | 159 ++++++++++++----- src/storage/keys.rs | 58 +------ src/storage/mod.rs | 11 +- src/storage/reader.rs | 86 ++++----- 16 files changed, 510 insertions(+), 504 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index f792ecd49..6d7cd3fd0 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -122,7 +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 entity ids together, visiting shared B+tree paths once while keeping the same exact-key leaf lookup as scalar reads. Temporary UUID hints leave the query cache and its 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 attribute scan has 25.6% lower p50 latency (256 → 190 ms); `docs/BENCHMARKS.md` records the paired runs and reproduction. +- **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 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. diff --git a/CLAUDE.md b/CLAUDE.md index caab43c16..ae1b580fb 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -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`, `get_many` (sorted exact lookups sharing child paths, #530), `MutexStorageBackend`) - - `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values; `uuids_of` shares exact-lookup tree paths for sorted id batches, #530) 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) @@ -216,7 +216,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1913 tests** (1898 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. diff --git a/README.md b/README.md index 79c75151f..e3ce418f1 100644 --- a/README.md +++ b/README.md @@ -269,7 +269,7 @@ 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 256 → 190 ms p50 after batched dictionary reads (#530); the other table scales were not remeasured in that comparison. +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. diff --git a/ROADMAP.md b/ROADMAP.md index 52e4e0f51..8851bce03 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -97,7 +97,7 @@ Scope — query API: - `lag` and `lead` window functions for the previous/next row within an ordered partition (#182; v3.0.0) - Bounded sliding row frames, `:rows N preceding`, for window aggregates (#183; v3.0.0, implemented on `v3`; builds on #182) - Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) runs every query and produces rows as they are pulled: patterns, expressions and pseudo-attributes (#544), joins and `:db/valid-at` (#545), `not` and `or` (#546), aggregates and windows (#547), rules (#548), and transaction reads (#550); the executor's query path is gone (#551; done on `v3`). Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549). -- Projected UUID lookup batches share DICT tree paths (#530; implemented on `v3`), keeping temporary memory bounded to a batch and query-cache charges in projection order. +- Projected UUID lookup batches walk dense DICT ranges (#530; implemented on `v3`), keeping temporary memory bounded to a batch and query-cache charges in projection order. - Native `:limit N`, `:order-by` and `:offset`, with a top-k `Sort` whose memory follows `N` (#306; done on `v3`, with the 10M-fact acceptance tests moved from #473; spec `docs/superpowers/specs/2026-10-24-limit-order-by-design.md`). Skipping the sort when an index already returns the rows in order is #641 (v3.next). - Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log pins its generation: checkpoints run but do not reuse its pages (#543; `API-013` deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462. - Read-only open: `OpenOptions::read_only` takes a shared lock, so several readers can hold a file at once, writes nothing to the file or its WAL (a WAL is applied in memory, a v7 file is read without migrating), and refuses writes with `API-014` (#429; Rust API done on `v3`). The bindings' `open_with_options` follows. diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index 1c507010f..2b8115e2c 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -9,41 +9,66 @@ Two rounds on an idle benchmark server, CPU and memory bound to the same NUMA node, running baseline then change and reversing the order in round two. Builds and tests finished before timing. Both libraries used `--profile envelope` (opt-level 3) and `-C force-frame-pointers=yes`. Queries opened checkpointed files -read-only and warmed their caches. Profiling ran separately. The table is the mean -of each round's p50; the [raw rounds](benchmarks/530-uuid-projection.jsonl) retain -run counts, maxima and the envelope's process-wide peak RSS. +read-only and warmed their caches. Profiling ran separately. The tables show the +mean of each broad round's p50; [raw results](benchmarks/530-uuid-projection.jsonl) +retain run counts, maxima and the envelope's process-wide peak RSS, plus the +repeated-ref follow-up described below. | Workload | Baseline p50 | Change p50 | Latency delta | |---|---:|---:|---:| -| Attribute scan, 1M facts / 166,666 rows | 255.58 ms | 190.07 ms | -25.6% | -| Point lookup, 1M facts / 1 row | 17.78 µs | 18.34 µs | +3.2% | -| Sparse entities, 1,000 rows | 2.90 ms | 2.57 ms | -11.4% | -| Random refs, 100,000 rows | 247.21 ms | 203.24 ms | -17.8% | -| Repeated refs, 100,000 rows | 87.24 ms | 75.43 ms | -13.5% | -| Two entity columns, 100,000 rows | 324.98 ms | 293.64 ms | -9.6% | -| Duplicate projected columns, 100,000 rows | 250.96 ms | 220.55 ms | -12.1% | - -The original 1M-fact envelope scan has **25.6% lower p50 latency**. Its process -peak RSS remains about 7 MiB in both versions. Point lookups remain around 18 µs; -the measured difference here is +0.56 µs. The other queries use a separate -300,000-fact fixture: 100,000 UUID entities with `:friend` pointing to -`(i * 7919 + 1) % 100000`, `:boss` to `i / 100`, and `:bucket` equal to `i % 100`. -Their expected row counts are checked on every run. Query workers use a 256 KiB -stack, including the two-column and duplicate-column cases. +| Attribute scan, 1M facts / 166,666 rows | 261.81 ms | 135.55 ms | -48.2% | +| Point lookup, 1M facts / 1 row | 19.08 µs | 18.23 µs | -4.4% | +| Sparse entities, 1,000 rows | 3.09 ms | 2.91 ms | -5.8% | +| Descending refs, 100,000 rows | 163.51 ms | 89.16 ms | -45.5% | +| Random refs, 100,000 rows | 388.97 ms | 279.13 ms | -28.2% | +| Repeated refs, 100,000 rows | 46.37 ms | 50.17 ms | +8.2% | +| Two entity columns, 100,000 rows | 524.05 ms | 474.02 ms | -9.5% | +| Duplicate columns, 100,000 rows | 396.10 ms | 284.36 ms | -28.2% | + +The original 1M-fact envelope scan has **48.2% lower p50 latency**. Its process +peak RSS remains about 7 MiB in both versions, about 0.2 MiB higher in the changed +runs. Point lookups remain around 18–19 µs. +The broad repeated-ref rounds varied, including one slower changed run. Four +additional interleaved pairs measured 45.55 → 45.78 ms (+0.5%); those records have +`phase: repeated_refs_recheck` and `trial` instead of `round` in the raw file. +The initial +8.2% result remains in the table and raw rounds. + +The reference queries use a separate 400,000-fact fixture: 100,000 UUID entities +with `:friend` pointing to `(i * 7919 + 1) % 100000`, `:boss` to `i / 100`, +`:reverse` to `99999 - i`, and `:bucket` equal to `i % 100`. Subject ids are assigned +and checked in order before any ref facts are added, making `:reverse` strictly +descending in internal-id order. Expected row counts are checked on every run. +Query workers use a 256 KiB stack, including the two-column and duplicate cases. | Probe | Query | |---|---| | Sparse entities | `[:find ?e :where [?e :bucket 7]]` | +| Descending refs | `[:find ?f :where [?e :reverse ?f]]` | | Random refs | `[:find ?f :where [?e :friend ?f]]` | | Repeated refs | `[:find ?f :where [?e :boss ?f]]` | | Two entity columns | `[:find ?e ?f :where [?e :friend ?f]]` | | Duplicate columns | `[:find ?f ?f :where [?e :friend ?f]]` | +A separate 8,895-fact fixture assigns 8,192 subject ids before adding Boolean +markers for the cutoff probes. A chunk is dense at 64 or more distinct ids with +numeric span at most twice its count. Small/sparse chunks use scalar exact reads; +dense chunks walk leaves. The 64-id dense cutoff adds about 7.6 µs here; the small +and sparse cases improve. This is a measured cost of the fixed cutoff. + +| Cutoff probe | Baseline p50 | Change p50 | Latency delta | +|---|---:|---:|---:| +| 63 ids, span 62 | 104.69 µs | 101.05 µs | -3.5% | +| 64 ids, span 128 (dense) | 105.62 µs | 113.27 µs | +7.2% | +| 64 ids, span 129 (sparse) | 116.87 µs | 115.45 µs | -1.2% | +| 512 ids, stride 16 (sparse) | 0.73 ms | 0.71 ms | -2.1% | + Separate user-cycle profiles of the 1M scan put scalar `DictReader::uuid_of` at -58.1% before the change and batched `DictReader::uuids_of` at 45.1% afterward. -The projection path shares B+tree descents; exact-key `leaf_get` still performs -individual leaf searches, preserving sparse-lookup behavior. Joins, collect-set -and sort/aggregate value conversions retain their existing scalar paths. +58.5% before the change and batched `DictReader::uuids_of` at 20.9% afterward. +Profile reports are retained locally. +Dense batches reuse the existing leaf cursor; sparse/small batches retain scalar +restart-point searches without a temporary per-id memo map. Sorted hints are +bounded to 1,024 distinct committed ids and keep cache/meter changes in projection +order. Joins, collect-set and sort/aggregate conversions retain their scalar paths. To reproduce, build both revisions once with the envelope profile and frame pointers. Compile the **same** [probe source](../scripts/uuid_projection_probe.rs) @@ -66,18 +91,25 @@ pointing to that directory and `bench_node` selecting one NUMA node: "$run_dir/baseline-envelope" __build "$run_dir/fixture-1m.graph" 1000000 \ > "$run_dir/fixture-1m.json" "$run_dir/baseline-probe" build "$run_dir/refs.graph" 100000 +"$run_dir/baseline-probe" build-boundaries "$run_dir/boundaries.graph" 8192 numactl --cpunodebind="$bench_node" --membind="$bench_node" \ "$run_dir/changed-envelope" __query "$run_dir/fixture-1m.graph" 2 8 60 numactl --cpunodebind="$bench_node" --membind="$bench_node" \ "$run_dir/changed-probe" query "$run_dir/refs.graph" \ '(query [:find ?f :where [?e :friend ?f]])' 100000 +numactl --cpunodebind="$bench_node" --membind="$bench_node" \ + "$run_dir/changed-probe" query "$run_dir/boundaries.graph" \ + '(query [:find ?e :where [?e :dense-threshold true]])' 64 ``` -Run the same cases with both executable pairs, sequentially; reverse the order -for the second round. The envelope warms three runs and measures up to 200 runs -or eight seconds; the reference probe warms three runs and measures up to 200 -runs or five seconds, at least five. Remove fixtures, executables and build -outputs after retaining the reports. +Run every case with both pairs sequentially, reversing the order for round two. +The envelope's arguments `2 8 60` select attribute scan, an eight-second budget +and a 60-second cap check; use `0 2 60` for point lookup. It warms three runs and +measures up to 200 runs or its budget, at least five. The reference probe warms +three runs and measures up to 20,000 runs or five seconds, at least five. The +higher cap gives small cutoff queries seconds of samples. For the repeated-ref +follow-up, run that query four additional pairs with alternating order. Remove +fixtures, executables and build outputs after retaining reports and CI passing. ## Bounded row frames (#183, unreleased) diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index aca160593..7474084a8 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,11 +4,11 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Passing** | 1,898 | 1,930 | +| **Passing** | 1,896 | 1,928 | | **Ignored** | 15 | 16 | -| **Total** | 1,913 | 1,946 | +| **Total** | 1,911 | 1,944 | -**Verified**: 2026-10-27 with `cargo test --quiet` (and `--features test-hooks`) on the designated bench machine, followed by focused engine reruns after the final projection review fix. +**Verified**: 2026-10-27 on the designated bench machine: the full default suite under branch coverage plus `cargo test --doc`, and `cargo test --features test-hooks`. The final review test enhancement also passed a focused dictionary rerun. All coverage gates retain their existing floors. #183 adds bounded row-frame parser, evaluator, and integration tests; one additional plan-independence case runs with `test-hooks`, including duplicate tie keys and NaN. A sliding-sum test checks recovery after integer saturation. Grammar corpus cases cover frame spellings and rejection. A meter test checks that a zero-width min frame reserves one deque slot. An ignored bench-machine diagnostic reproduces the Criterion datasets and prints the engine meter's peak for every measured case. @@ -346,7 +346,7 @@ These tests compare the database against an independent answer rather than a sin ## Query Engine -- **Batched projected UUIDs** (#530; 13 tests): B+tree dense/sparse read-count comparison with scalar lookups, empty/invalid input, callback failure and cycles; DICT scalar agreement across chunks and sparse ids, missing/malformed requested entries and unrelated malformed values; fixed key bytes and integer-boundary ordering; committed/pending/repeated projection and duplicate columns; speculative fallback, memory refusal and scalar error order; unused entity/count queries inspected before cache release; counted scalar/speculative hidden-entity reads; duplicate-slot reclamation and bounded sorting of repeated ids; a zero-cache guard for the on-disk batch override. +- **Batched projected UUIDs** (#530; 11 tests): DICT scalar agreement across dense multi-chunk and sparse/small batches, empty/invalid input, missing/malformed requested entries and unrelated malformed values, callback failure, wrong pages and cycles; a zero-cache reader guard compares results and reads at 63/64 ids and spans of `2c`/`2c+1`; committed/pending/repeated projection and duplicate columns; partial speculative fallback, memory refusal and scalar error order; unused entity/count queries inspected before cache release; a sorted-buffer model checks ascending, descending, repeated and shuffled ids across capacity boundaries. - **Engine paths** (`query::engine::tests`, #473, #544) - Reaches every index choice; net-assert of pending records over committed ones; `:as-of`; valid time; long strings and reads of several batches, in memory, across checkpoints and after reopen. diff --git a/docs/benchmarks/530-uuid-projection.jsonl b/docs/benchmarks/530-uuid-projection.jsonl index af950473a..dda18efb6 100644 --- a/docs/benchmarks/530-uuid-projection.jsonl +++ b/docs/benchmarks/530-uuid-projection.jsonl @@ -1,28 +1,56 @@ -{"max_ms": 269.36647000000005, "name": "attribute_scan", "p50_ms": 257.05593700000003, "p99_ms": 269.36647000000005, "peak_rss_kb": 7332, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 31, "round": 1, "version": "baseline", "workload": "attribute_scan_1m"} -{"max_ms": 0.035408999999999996, "name": "point_entity", "p50_ms": 0.018000000000000002, "p99_ms": 0.025644, "peak_rss_kb": 5036, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 1, "version": "baseline", "workload": "point_1m"} -{"runs": 200.0, "p50_ms": 2.905018, "max_ms": 3.485532, "rows": 1000.0, "round": 1, "version": "baseline", "workload": "sparse_entities", "stack_bytes": 262144} -{"runs": 21.0, "p50_ms": 246.781251, "max_ms": 257.312645, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "random_refs", "stack_bytes": 262144} -{"runs": 57.0, "p50_ms": 87.125893, "max_ms": 124.227527, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "repeated_refs", "stack_bytes": 262144} -{"runs": 16.0, "p50_ms": 325.925679, "max_ms": 334.407692, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "two_entity_columns", "stack_bytes": 262144} -{"runs": 20.0, "p50_ms": 250.833874, "max_ms": 261.470668, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "duplicate_columns", "stack_bytes": 262144} -{"max_ms": 201.10414400000002, "name": "attribute_scan", "p50_ms": 189.973728, "p99_ms": 201.10414400000002, "peak_rss_kb": 7336, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 42, "round": 1, "version": "changed", "workload": "attribute_scan_1m"} -{"max_ms": 0.029326, "name": "point_entity", "p50_ms": 0.01808, "p99_ms": 0.022223, "peak_rss_kb": 5196, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 1, "version": "changed", "workload": "point_1m"} -{"runs": 200.0, "p50_ms": 2.564409, "max_ms": 2.952247, "rows": 1000.0, "round": 1, "version": "changed", "workload": "sparse_entities", "stack_bytes": 262144} -{"runs": 25.0, "p50_ms": 203.333696, "max_ms": 253.693786, "rows": 100000.0, "round": 1, "version": "changed", "workload": "random_refs", "stack_bytes": 262144} -{"runs": 67.0, "p50_ms": 75.329937, "max_ms": 82.618074, "rows": 100000.0, "round": 1, "version": "changed", "workload": "repeated_refs", "stack_bytes": 262144} -{"runs": 18.0, "p50_ms": 288.149341, "max_ms": 307.092977, "rows": 100000.0, "round": 1, "version": "changed", "workload": "two_entity_columns", "stack_bytes": 262144} -{"runs": 23.0, "p50_ms": 221.045346, "max_ms": 227.356607, "rows": 100000.0, "round": 1, "version": "changed", "workload": "duplicate_columns", "stack_bytes": 262144} -{"max_ms": 243.255707, "name": "attribute_scan", "p50_ms": 190.17330900000002, "p99_ms": 243.255707, "peak_rss_kb": 7404, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 42, "round": 2, "version": "changed", "workload": "attribute_scan_1m"} -{"max_ms": 0.041279, "name": "point_entity", "p50_ms": 0.018599, "p99_ms": 0.033733, "peak_rss_kb": 5228, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 2, "version": "changed", "workload": "point_1m"} -{"runs": 200.0, "p50_ms": 2.574066, "max_ms": 3.074476, "rows": 1000.0, "round": 2, "version": "changed", "workload": "sparse_entities", "stack_bytes": 262144} -{"runs": 25.0, "p50_ms": 203.154536, "max_ms": 211.01008, "rows": 100000.0, "round": 2, "version": "changed", "workload": "random_refs", "stack_bytes": 262144} -{"runs": 66.0, "p50_ms": 75.52819, "max_ms": 82.607256, "rows": 100000.0, "round": 2, "version": "changed", "workload": "repeated_refs", "stack_bytes": 262144} -{"runs": 17.0, "p50_ms": 299.12337, "max_ms": 336.420854, "rows": 100000.0, "round": 2, "version": "changed", "workload": "two_entity_columns", "stack_bytes": 262144} -{"runs": 23.0, "p50_ms": 220.052204, "max_ms": 226.823264, "rows": 100000.0, "round": 2, "version": "changed", "workload": "duplicate_columns", "stack_bytes": 262144} -{"max_ms": 267.881656, "name": "attribute_scan", "p50_ms": 254.108311, "p99_ms": 267.881656, "peak_rss_kb": 7192, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 32, "round": 2, "version": "baseline", "workload": "attribute_scan_1m"} -{"max_ms": 0.038784, "name": "point_entity", "p50_ms": 0.017550999999999997, "p99_ms": 0.033002000000000004, "peak_rss_kb": 5080, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 2, "version": "baseline", "workload": "point_1m"} -{"runs": 200.0, "p50_ms": 2.893398, "max_ms": 3.416504, "rows": 1000.0, "round": 2, "version": "baseline", "workload": "sparse_entities", "stack_bytes": 262144} -{"runs": 21.0, "p50_ms": 247.645778, "max_ms": 254.405355, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "random_refs", "stack_bytes": 262144} -{"runs": 57.0, "p50_ms": 87.357368, "max_ms": 94.99944, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "repeated_refs", "stack_bytes": 262144} -{"runs": 16.0, "p50_ms": 324.02794, "max_ms": 332.723497, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "two_entity_columns", "stack_bytes": 262144} -{"runs": 20.0, "p50_ms": 251.088229, "max_ms": 259.18302, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "duplicate_columns", "stack_bytes": 262144} +{"max_ms": 268.828736, "name": "attribute_scan", "p50_ms": 256.394526, "p99_ms": 268.828736, "peak_rss_kb": 7144, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 32, "round": 1, "version": "baseline", "workload": "attribute_scan_1m"} +{"max_ms": 0.039694, "name": "point_entity", "p50_ms": 0.020107, "p99_ms": 0.034064, "peak_rss_kb": 4964, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 1, "version": "baseline", "workload": "point_1m"} +{"runs": 1624.0, "p50_ms": 3.058812, "max_ms": 10.409856, "rows": 1000.0, "round": 1, "version": "baseline", "workload": "sparse_entities", "stack_bytes": 262144} +{"runs": 32.0, "p50_ms": 160.439578, "max_ms": 166.502422, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "descending_refs", "stack_bytes": 262144} +{"runs": 14.0, "p50_ms": 376.274772, "max_ms": 432.101896, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "random_refs", "stack_bytes": 262144} +{"runs": 109.0, "p50_ms": 45.636074, "max_ms": 52.423149, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "repeated_refs", "stack_bytes": 262144} +{"runs": 10.0, "p50_ms": 508.509389, "max_ms": 517.983229, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "two_entity_columns", "stack_bytes": 262144} +{"runs": 13.0, "p50_ms": 383.466034, "max_ms": 391.815829, "rows": 100000.0, "round": 1, "version": "baseline", "workload": "duplicate_columns", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.102628, "max_ms": 0.363832, "rows": 63.0, "round": 1, "version": "baseline", "workload": "below_threshold_63", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.105814, "max_ms": 1.327837, "rows": 64.0, "round": 1, "version": "baseline", "workload": "dense_threshold_64_span128", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.116621, "max_ms": 20.867481, "rows": 64.0, "round": 1, "version": "baseline", "workload": "above_threshold_64_span129", "stack_bytes": 262144} +{"runs": 6840.0, "p50_ms": 0.724178, "max_ms": 6.258705, "rows": 512.0, "round": 1, "version": "baseline", "workload": "large_sparse_512", "stack_bytes": 262144} +{"max_ms": 142.44949200000002, "name": "attribute_scan", "p50_ms": 134.898792, "p99_ms": 142.44949200000002, "peak_rss_kb": 7400, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 60, "round": 1, "version": "changed", "workload": "attribute_scan_1m"} +{"max_ms": 0.044066999999999995, "name": "point_entity", "p50_ms": 0.018122, "p99_ms": 0.032955, "peak_rss_kb": 5064, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 1, "version": "changed", "workload": "point_1m"} +{"runs": 1711.0, "p50_ms": 2.909833, "max_ms": 9.901581, "rows": 1000.0, "round": 1, "version": "changed", "workload": "sparse_entities", "stack_bytes": 262144} +{"runs": 56.0, "p50_ms": 89.212431, "max_ms": 99.510069, "rows": 100000.0, "round": 1, "version": "changed", "workload": "descending_refs", "stack_bytes": 262144} +{"runs": 18.0, "p50_ms": 279.353679, "max_ms": 328.512266, "rows": 100000.0, "round": 1, "version": "changed", "workload": "random_refs", "stack_bytes": 262144} +{"runs": 93.0, "p50_ms": 53.604552, "max_ms": 61.181445, "rows": 100000.0, "round": 1, "version": "changed", "workload": "repeated_refs", "stack_bytes": 262144} +{"runs": 11.0, "p50_ms": 473.215701, "max_ms": 480.50225, "rows": 100000.0, "round": 1, "version": "changed", "workload": "two_entity_columns", "stack_bytes": 262144} +{"runs": 18.0, "p50_ms": 283.746947, "max_ms": 290.329612, "rows": 100000.0, "round": 1, "version": "changed", "workload": "duplicate_columns", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.100713, "max_ms": 1.516028, "rows": 63.0, "round": 1, "version": "changed", "workload": "below_threshold_63", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.112941, "max_ms": 0.321017, "rows": 64.0, "round": 1, "version": "changed", "workload": "dense_threshold_64_span128", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.115224, "max_ms": 1.520681, "rows": 64.0, "round": 1, "version": "changed", "workload": "above_threshold_64_span129", "stack_bytes": 262144} +{"runs": 7021.0, "p50_ms": 0.706296, "max_ms": 6.767843, "rows": 512.0, "round": 1, "version": "changed", "workload": "large_sparse_512", "stack_bytes": 262144} +{"max_ms": 147.446253, "name": "attribute_scan", "p50_ms": 136.208132, "p99_ms": 147.446253, "peak_rss_kb": 7340, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 59, "round": 2, "version": "changed", "workload": "attribute_scan_1m"} +{"max_ms": 0.041617, "name": "point_entity", "p50_ms": 0.018338999999999998, "p99_ms": 0.036269, "peak_rss_kb": 5216, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 2, "version": "changed", "workload": "point_1m"} +{"runs": 1707.0, "p50_ms": 2.915797, "max_ms": 10.235462, "rows": 1000.0, "round": 2, "version": "changed", "workload": "sparse_entities", "stack_bytes": 262144} +{"runs": 56.0, "p50_ms": 89.103746, "max_ms": 114.84222, "rows": 100000.0, "round": 2, "version": "changed", "workload": "descending_refs", "stack_bytes": 262144} +{"runs": 18.0, "p50_ms": 278.909567, "max_ms": 285.061218, "rows": 100000.0, "round": 2, "version": "changed", "workload": "random_refs", "stack_bytes": 262144} +{"runs": 107.0, "p50_ms": 46.74243, "max_ms": 54.337, "rows": 100000.0, "round": 2, "version": "changed", "workload": "repeated_refs", "stack_bytes": 262144} +{"runs": 11.0, "p50_ms": 474.821155, "max_ms": 481.438394, "rows": 100000.0, "round": 2, "version": "changed", "workload": "two_entity_columns", "stack_bytes": 262144} +{"runs": 18.0, "p50_ms": 284.981626, "max_ms": 330.69007, "rows": 100000.0, "round": 2, "version": "changed", "workload": "duplicate_columns", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.10138, "max_ms": 1.46641, "rows": 63.0, "round": 2, "version": "changed", "workload": "below_threshold_63", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.113592, "max_ms": 1.738096, "rows": 64.0, "round": 2, "version": "changed", "workload": "dense_threshold_64_span128", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.115684, "max_ms": 0.378427, "rows": 64.0, "round": 2, "version": "changed", "workload": "above_threshold_64_span129", "stack_bytes": 262144} +{"runs": 6805.0, "p50_ms": 0.716166, "max_ms": 4.992522, "rows": 512.0, "round": 2, "version": "changed", "workload": "large_sparse_512", "stack_bytes": 262144} +{"max_ms": 276.102579, "name": "attribute_scan", "p50_ms": 267.23276200000004, "p99_ms": 276.102579, "peak_rss_kb": 7204, "query": "[:find ?e ?a :where [?e :age ?a]]", "rows": 166666, "runs": 31, "round": 2, "version": "baseline", "workload": "attribute_scan_1m"} +{"max_ms": 0.06305100000000001, "name": "point_entity", "p50_ms": 0.018045000000000002, "p99_ms": 0.051058, "peak_rss_kb": 5012, "query": "[:find ?a :where [:p83333 :age ?a]]", "rows": 1, "runs": 200, "round": 2, "version": "baseline", "workload": "point_1m"} +{"runs": 1551.0, "p50_ms": 3.124614, "max_ms": 10.419288, "rows": 1000.0, "round": 2, "version": "baseline", "workload": "sparse_entities", "stack_bytes": 262144} +{"runs": 31.0, "p50_ms": 166.574827, "max_ms": 171.091818, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "descending_refs", "stack_bytes": 262144} +{"runs": 13.0, "p50_ms": 401.666236, "max_ms": 412.279299, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "random_refs", "stack_bytes": 262144} +{"runs": 106.0, "p50_ms": 47.105065, "max_ms": 70.723039, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "repeated_refs", "stack_bytes": 262144} +{"runs": 10.0, "p50_ms": 539.590475, "max_ms": 576.3014, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "two_entity_columns", "stack_bytes": 262144} +{"runs": 13.0, "p50_ms": 408.73038, "max_ms": 416.263488, "rows": 100000.0, "round": 2, "version": "baseline", "workload": "duplicate_columns", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.106749, "max_ms": 1.480242, "rows": 63.0, "round": 2, "version": "baseline", "workload": "below_threshold_63", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.105426, "max_ms": 0.354671, "rows": 64.0, "round": 2, "version": "baseline", "workload": "dense_threshold_64_span128", "stack_bytes": 262144} +{"runs": 20000.0, "p50_ms": 0.117125, "max_ms": 1.230802, "rows": 64.0, "round": 2, "version": "baseline", "workload": "above_threshold_64_span129", "stack_bytes": 262144} +{"runs": 6580.0, "p50_ms": 0.728981, "max_ms": 6.7739, "rows": 512.0, "round": 2, "version": "baseline", "workload": "large_sparse_512", "stack_bytes": 262144} +{"runs": 109.0, "p50_ms": 45.617917, "max_ms": 53.738156, "rows": 100000.0, "trial": 1, "version": "baseline", "workload": "repeated_refs", "phase": "repeated_refs_recheck"} +{"runs": 109.0, "p50_ms": 45.717864, "max_ms": 53.198411, "rows": 100000.0, "trial": 1, "version": "changed", "workload": "repeated_refs", "phase": "repeated_refs_recheck"} +{"runs": 109.0, "p50_ms": 45.816751, "max_ms": 53.986346, "rows": 100000.0, "trial": 2, "version": "changed", "workload": "repeated_refs", "phase": "repeated_refs_recheck"} +{"runs": 109.0, "p50_ms": 45.558309, "max_ms": 68.157225, "rows": 100000.0, "trial": 2, "version": "baseline", "workload": "repeated_refs", "phase": "repeated_refs_recheck"} +{"runs": 110.0, "p50_ms": 45.545034, "max_ms": 53.054791, "rows": 100000.0, "trial": 3, "version": "baseline", "workload": "repeated_refs", "phase": "repeated_refs_recheck"} +{"runs": 109.0, "p50_ms": 45.718574, "max_ms": 53.693513, "rows": 100000.0, "trial": 3, "version": "changed", "workload": "repeated_refs", "phase": "repeated_refs_recheck"} +{"runs": 109.0, "p50_ms": 45.883954, "max_ms": 53.587033, "rows": 100000.0, "trial": 4, "version": "changed", "workload": "repeated_refs", "phase": "repeated_refs_recheck"} +{"runs": 110.0, "p50_ms": 45.483202, "max_ms": 53.33047, "rows": 100000.0, "trial": 4, "version": "baseline", "workload": "repeated_refs", "phase": "repeated_refs_recheck"} diff --git a/docs/superpowers/plans/2026-10-27-dict-batch.md b/docs/superpowers/plans/2026-10-27-dict-batch.md index c1b73e452..a8f0d3f68 100644 --- a/docs/superpowers/plans/2026-10-27-dict-batch.md +++ b/docs/superpowers/plans/2026-10-27-dict-batch.md @@ -1,39 +1,49 @@ # #530 implementation plan -Spec: `../specs/2026-10-27-dict-batch-design.md`. Claude approved the spec and plan -on 2026-10-27 before implementation. Base: `80120758`, branch `perf/530-dict-batch`. +Spec: `../specs/2026-10-27-dict-batch-design.md`. Claude reviewed the original +spec/plan and the size-driven revision before implementation on 2026-10-27. +Base: `80120758`, branch `perf/530-dict-batch`. -1. Profile the current 1M-fact attribute scan on the idle benchmark server, envelope profile - and frame pointers. Keep a baseline executable and identical fixtures. -2. Create the ignored `.worktrees/530-dict-batch` worktree from `origin/v3`. -3. Add B+tree batch correctness/read-count regressions. Establish failure using - scalar fallback, then implement child-grouped descent with scalar `leaf_get`. - Observed: the dense read-count assertion failed with scalar lookup; all three - B+tree regressions then passed with grouped descent. -4. Add fixed DICT key and UUID batch tests; implement bounded key encoding, - `DictReader::uuids_of`, the default `KeySource` method and on-disk override. -5. Add projection regressions. Observe that mixed-id and fallback tests fail - before batching; implement bounded stack hints, scalar-order insertion and - fallback. Add the unused-entity/count guard before `end_pull`. -6. Run full default and `test-hooks` tests, CI clippy, and formatting checks on the - bench (formatting may also run locally). Keep heavy work off the laptop. -7. Build the optimized envelope and matching probe, then alternate baseline and - change timings on an idle machine. Check sparse/random/repeated projections, - a 256 KiB worker stack and point reads. Profile separately from timing. -8. Synchronize changelog, benchmark evidence, roadmap, architecture notes and - test counts; cross-check README and docs-site claims. Do not bump versions. -9. Get Claude's final review, address findings, and verify affected work before - opening the `v3` PR. Save logs locally, then remove every task-owned bench - fixture, executable, target and scratch directory. +1. Profile the 1M-fact attribute scan on the idle bench with the envelope profile + and frame pointers. Preserve the baseline executable and identical fixtures. +2. Use the isolated `.worktrees/530-dict-batch` worktree from `origin/v3`. +3. Add dictionary/reader correctness and zero-cache read-count regressions. + Establish the dense read-count failure with scalar lookup, then implement + bounded dense leaf walks and sparse/small exact reads with shared decoding. +4. Add projection regressions before batching: mixed ids and fallback fail + without it. Implement bounded stack hints, scalar-order cache insertion and + all-or-nothing fallback. Guard unused entities/count before `end_pull`. +5. Maintain sorted distinct hints by bounded binary insertion. Model-check the + buffer against a set at capacity boundaries, including descending and repeated + inputs; repeated ids must not force sorting or consume duplicate slots. +6. Cover partial callback failure, missing/malformed requested values, skipped + malformed values, wrong pages and cycles. Compare reader results and raw reads + at 63/64 ids and spans `2c`/`2c+1`. Keep B+tree/key production code unchanged. +7. Run full default and `test-hooks` suites, CI clippy, coverage and release-size + gates on the bench. Preserve the existing coverage floors and 1,230 KiB cap. +8. Rebuild the optimized envelope and the same public-API probe against both + libraries. Assign subject ids before refs to make reverse refs strictly + descending. Alternate baseline/change timings on an idle, NUMA-pinned bench; + cover the original scan, point, sparse, density thresholds, descending/random/ + repeated refs and multiple columns on a 256 KiB worker stack. Profile apart. +9. Synchronize changelog, benchmarks/raw data, roadmap, module notes and test + counts; cross-check README and docs-site claims without a version bump. +10. Obtain Claude's final review, resolve findings, push the `v3` PR follow-up and + docs-site PR. Retain scratch until CI is green, save logs locally, then remove + every task-owned bench fixture, executable, target and scratch directory. -Implementation review follow-up: compact duplicate hint cells before enforcing -the distinct-id cap (regression observed failing, then passing); count both scalar -and speculative reads for hidden entity cells; test every integer byte boundary; -guard the on-disk override with a zero-cache read-count test. Fsync-heavy broad suites run sequentially after contention; timing runs are -pinned to one NUMA node on the idle benchmark server. Incomplete interrupted runs do not count as verification. +CI follow-up: the initial generic batch walker exceeded the unchanged binary +budget and introduced coverage gaps. Claude approved reusing `LeafCursor` only +for dense chunks and scalar restart-point reads otherwise, removing the generic +walker, encoder helper and unused trait default. Test-only counting-backend reuse +avoids duplicate unexercised backend methods. The final design also avoids a +new general sort specialization in the embedded binary. -The final review approved the implementation conditional on remaining checks. -Its repeated-id cost note was also addressed: a sort-count regression failed -before the buffer reused its sorted prefix, then passed with all six projection -tests. Full default and test-hooks runs passed; final focused checks cover this -last local optimization. +Small-query follow-up: the original 200-iteration cap produced only about 20 ms +of samples for the threshold cases. A longer probe and profiles did not reproduce +the apparent slowdown. Increase the public probe cap to 20,000 iterations and +repeat both A/B rounds; keep timing separate from profiling. + +Claude approved the final code, evidence and documentation after reviewing the +64-id cutoff cost and repeated-ref variability. Final CI and bench cleanup follow +the push; no budget or coverage-floor exception was needed. diff --git a/docs/superpowers/specs/2026-10-27-dict-batch-design.md b/docs/superpowers/specs/2026-10-27-dict-batch-design.md index 258f36aff..167a97b58 100644 --- a/docs/superpowers/specs/2026-10-27-dict-batch-design.md +++ b/docs/superpowers/specs/2026-10-27-dict-batch-design.md @@ -1,72 +1,72 @@ -# Batched UUID projection (#530) +# #530: batch projected UUID lookups -Approved after Claude spec/plan review, 2026-10-27. Targets `v3`, format v8. +Date: 2026-10-27. Base: `v3` at `80120758`. ## Problem -The streaming engine carries DICT ids until projection, but a scan returning a -different entity in every row still performs one root-to-leaf DICT lookup per -UUID. At `80120758`, the 1M-fact envelope attribute scan spends about 58% of -sampled user cycles under `DictReader::uuid_of` on the idle bench machine. +The streaming engine keeps internal ids through scans and operators, but returned +entity/ref cells still cause a root-to-leaf DICT lookup for each distinct id. +The original 1M-fact attribute scan spends most of its time in this conversion. +Resolve projected ids together without retaining a whole-query dictionary cache. ## Design -`Project` resolves up to 1,024 committed entity cache misses from its returned -columns as one sorted, distinct batch. Duplicate cells are compacted when the -fixed buffer fills so they do not consume its distinct-id bound. Its temporary UUID hints live on the -stack. Pending/provisional ids and existing cache hits are excluded using the -same routing predicate as scalar `IdSpace::uuid`. One distinct miss, no misses, -and in-memory queries stay on the scalar path. +`Project` collects at most 1,024 distinct committed UUID-cache misses from the +returned cells. A preflight avoids initializing hints when fewer than two ids +need conversion. A fixed stack buffer maintains sorted, distinct ids using +binary search and insertion; repeated ids move nothing. Once full, remaining +ids use ordinary scalar conversion. Pending/provisional ids never read DICT. -`KeySource::uuids_of` is an additive default method: strictly increasing ids, -callbacks in that order, empty input reads nothing. Its default implementation -calls scalar `uuid_of`. `OnDiskReader` overrides it using the query's same pinned -DICT root, never a newer database state. `DictReader` encodes the ids into a -bounded fixed-size key buffer, then calls `btree::get_many`. +`KeySource::uuids_of` is an internal required method. The pinned `OnDiskReader` +forwards to `DictReader::uuids_of`; no public API or retained reader fields change. +The dictionary checks sorted/distinct input and processes chunks of at most +1,024 ids. A chunk with at least 64 ids and numeric span at most twice its count +uses the existing `LeafCursor`: seek once to its first key, then advance through +leaves, decode integer keys and parse UUIDs only for requested ids. There is no +per-id key encoding; transient leaf decoding is bounded to one leaf plus its +path. Stop at the last requested id or the end of the eid +prefix. The density bound limits the skipped entries. Sparse/small chunks use +existing exact-key B+tree reads, preserving restart-point leaf searches. Both +paths skip the scalar reader's temporary memo map and share UUID decoding. +There are no production changes to the B+tree or key encoding. -`get_many` groups sorted keys by each internal node's child range, visits every -required page once, and calls today's `leaf_get` for each requested key. It -retains the scalar leaf restart-point behavior rather than decoding full leaves. -Sparse keys do not cause more backend page reads than scalar lookups. Recursion -has scalar `get`'s 32-level bound. Empty and invalid input do no reads. Unsorted -or duplicate keys are the existing internal invariant violation, `INT-049`. -Missing or malformed requested UUIDs are scalar's existing `STG-036`; unrelated -UUID values are never parsed. Fixed DICT keys preserve the existing byte format, -including integer-length boundaries. +Hints do not populate `IdSpace` or charge its meter. Each returned cell consumes +its hint or scalar lookup in the original row/column order, then performs the +original memory charge, allocation and cache insertion. Any failed or incomplete +speculative read discards all hints. Scalar errors remain authoritative: a later +bad id or budget refusal cannot displace an earlier value error. A dense walk can +encounter corruption in skipped leaves; its error causes scalar fallback rather +than changing the query result. `verify()` remains responsible for unrelated +corruption. `end_pull` still releases committed lookup maps. -Hints do not populate `IdSpace` or charge its meter. When each returned cell is -converted, `uuid_with_hint` uses its hint or the scalar lookup and performs the -original charge, allocation and map insertion in row/column order. A failed or -incomplete speculative read discards all hints. Scalar errors remain authoritative, -so a later bad id or budget refusal cannot displace an earlier value error. -`end_pull` still releases committed lookup maps. No fields or retained caches are -added to the stream, reader or id space. Stack buffers are bounded independently -of database size; the heap memory meter continues counting retained query state. +No fields or retained caches are added to the stream, reader or id space. Stack +buffers are bounded independently of database size; the heap memory meter counts +retained query state. A 256 KiB worker-stack probe covers the projection cases. ## Boundaries and philosophy -The change optimizes projected entity/ref cells. Joins, collect-set, sorting and -aggregate value conversions retain their existing lookup behavior. It adds no -configuration, dependencies, file-format changes or release bump. Sharing exact -lookups while preserving scalar behavior follows the embedded, portable, -reliability-first design. It does not introduce a cache that grows with a query's -whole answer. +This optimizes projected entity/ref cells. Joins, collect-set, sorting and +aggregate value conversions keep their existing lookup behavior. It adds no +configuration, dependencies, file-format changes or version bump. Reusing +existing tree primitives with bounded temporary memory follows the embedded, +portable, reliability-first philosophy. The unchanged 1,230 KiB binary-size cap +and coverage floors are acceptance requirements. ## Acceptance -- Dense lookup batches read shared tree paths once; sparse batches read no more - pages than scalar; empty/invalid inputs, missing keys, callbacks and cycles are - covered by deterministic tests with a disabled page cache. -- Requested UUIDs match scalar over sparse and multi-chunk subsets; unrelated - malformed values do not fail the batch; fixed encodings keep byte order. -- Projection batches committed ids even when pending/provisional ids share a - batch; repeated refs, duplicate columns, row order, fallback, memory charging - and earlier scalar errors remain correct. -- A scan which does not project entities, including a count, performs no entity - conversion before cache release. Existing multi-batch and generation-pin tests - continue to pass. -- Default and `test-hooks` suites and CI clippy run on the bench. Idle sequential - A/B measurements pinned to one NUMA node cover the original 1M scan, point reads, sparse entities and - random/repeated ref projections; profiles and timings run separately. -- Claude reviews the implementation before a PR targeting `v3`. Bench scratch - files are removed after retaining local verification evidence. +- Dense batches share tree/leaf reads; sparse batches read no more pages than + scalar. Compare results and raw reads with cache disabled at 63/64 ids and + spans of `2c`/`2c+1`, as well as sparse and multi-chunk subsets. +- Cover empty/invalid input, requested missing/malformed UUIDs, unrelated malformed + values, callback errors after partial output, wrong page types and cycles. +- Cover committed/pending/repeated projection, duplicate columns, row order, + fallback, memory charging and earlier scalar errors. Check the sorted buffer + against a set for ascending, descending, repeated and shuffled inputs. +- Queries without projected entities, including count, do no entity conversion + before cache release. Existing multi-batch/generation-pin tests still pass. +- Run default and `test-hooks` suites, clippy, release size and coverage gates on + the bench. Run idle, sequential A/B timings pinned to one NUMA node, including + the original 1M scan, point reads, sparse/dense-threshold and descending/random/ + repeated refs. Profile separately from timing. +- Obtain Claude spec/plan and final reviews. Target `v3`; keep benchmark scratch + until CI is green, retain reports locally, then remove task-owned bench files. diff --git a/scripts/uuid_projection_probe.rs b/scripts/uuid_projection_probe.rs index 60c061a02..31fbbae86 100644 --- a/scripts/uuid_projection_probe.rs +++ b/scripts/uuid_projection_probe.rs @@ -2,10 +2,11 @@ //! //! Compile against either comparison library with rustc (docs/BENCHMARKS.md). //! Usage: probe build +//! probe build-boundaries 8192 //! probe query '' //! Query timings exclude file open and thread creation; the worker stack is 256 KiB. -use minigraf::{Minigraf, OpenOptions}; +use minigraf::{Minigraf, OpenOptions, Value}; use std::time::{Duration, Instant}; fn uuid(i: usize) -> String { @@ -13,17 +14,75 @@ fn uuid(i: usize) -> String { } fn main() { let args: Vec<_> = std::env::args().collect(); - if args[1] == "build" { + if args[1] == "build" || args[1] == "build-boundaries" { + let boundaries = args[1] == "build-boundaries"; let n: usize = args[3].parse().unwrap(); assert!( !std::path::Path::new(&args[2]).exists(), "fixture must be built from scratch" ); let db = Minigraf::open(&args[2]).unwrap(); + // Assign every subject id first, making :reverse strictly descending + // in the covering index's entity-id order. for start in (0..n).step_by(1000) { let mut command = String::from("(transact ["); for i in start..(start + 1000).min(n) { - command.push_str(&format!("[#uuid \"{}\" :friend #uuid \"{}\"] [#uuid \"{}\" :boss #uuid \"{}\"] [#uuid \"{}\" :bucket {}]", uuid(i), uuid((i*7919+1)%n), uuid(i), uuid(i/100), uuid(i), i%100)); + command.push_str(&format!("[#uuid \"{}\" :bucket {}]", uuid(i), i % 100)); + } + command.push_str("])"); + db.execute(&command).unwrap(); + } + db.checkpoint().unwrap(); + let mut cursor = db + .query("(query [:find ?e :where [?e :bucket ?v]])") + .unwrap(); + let mut seen = 0; + while let Some(batch) = cursor.next_batch(1000).unwrap() { + for row in batch.rows() { + assert!( + matches!(row.first(), Some(Value::Ref(id)) if id.to_string() == uuid(seen)), + "fixture ids must be assigned in subject order" + ); + seen += 1; + } + } + assert_eq!(seen, n); + drop(cursor); + for start in (0..n).step_by(1000) { + let mut command = String::from("(transact ["); + for i in start..(start + 1000).min(n) { + if boundaries { + for (attribute, include) in [ + ("below-threshold", i < 63), + ("dense-threshold", (i < 126 && i % 2 == 0) || i == 128), + ("above-threshold", (i < 126 && i % 2 == 0) || i == 129), + ("large-sparse", i % 16 == 0), + ] { + if include { + command.push_str(&format!( + "[#uuid \"{}\" :{} true]", + uuid(i), + attribute + )); + } + } + continue; + } + command.push_str(&format!( + "[#uuid \"{}\" :friend #uuid \"{}\"]", + uuid(i), + uuid((i * 7919 + 1) % n) + )); + command.push_str(&format!( + "[#uuid \"{}\" :boss #uuid \"{}\"]", + uuid(i), + uuid(i / 100) + )); + command.push_str(&format!( + "[#uuid \"{}\" :reverse #uuid \"{}\"]", + uuid(i), + uuid(n - 1 - i) + )); } command.push_str("])"); db.execute(&command).unwrap(); @@ -53,7 +112,8 @@ fn main() { } let start = Instant::now(); let mut times = Vec::new(); - while times.len() < 200 && (times.len() < 5 || start.elapsed() < Duration::from_secs(5)) + while times.len() < 20_000 + && (times.len() < 5 || start.elapsed() < Duration::from_secs(5)) { let t = Instant::now(); drain(); diff --git a/src/query/engine/project.rs b/src/query/engine/project.rs index e0738a391..3106d1185 100644 --- a/src/query/engine/project.rs +++ b/src/query/engine/project.rs @@ -10,11 +10,6 @@ use super::cell::{Cell, Scalar}; use crate::graph::types::{Value, ValueSet}; use anyhow::Result; -#[cfg(test)] -thread_local! { - static HINT_SORTS: std::cell::Cell = const { std::cell::Cell::new(0) }; -} - /// The rows of `batch`, with the cells of the slots `find` as values. pub(crate) fn project(batch: &Batch, find: &[usize], ctx: &mut Ctx<'_>) -> Result>> { let hints = Uuids::read(batch, find, ctx); @@ -70,25 +65,11 @@ impl Uuids { values: [crate::graph::types::EntityId::nil(); BATCH_ROWS], len: 0, }; - let mut sorted = 0; for eid in candidates() { - if hints.ids.get(..sorted)?.binary_search(&eid).is_ok() { - continue; - } - if hints.len == BATCH_ROWS { - hints.compact()?; - sorted = hints.len; - if hints.len == BATCH_ROWS { - break; - } - if hints.ids.get(..sorted)?.binary_search(&eid).is_ok() { - continue; - } + if !hints.insert(eid)? { + break; } - *hints.ids.get_mut(hints.len)? = eid; - hints.len += 1; } - hints.compact()?; let count = hints.len; if count < 2 { return None; @@ -118,24 +99,21 @@ impl Uuids { (read == count).then_some(hints) } - /// Reclaim duplicate slots before deciding the distinct-id bound is full. - fn compact(&mut self) -> Option<()> { - let ids = self.ids.get_mut(..self.len)?; - #[cfg(test)] - HINT_SORTS.with(|n| n.set(n.get() + 1)); - ids.sort_unstable(); - let mut count = 0; - let mut previous = None; - for i in 0..ids.len() { - let eid = *ids.get(i)?; - if previous != Some(eid) { - *ids.get_mut(count)? = eid; - count += 1; - previous = Some(eid); - } + /// Keep the bounded buffer sorted and distinct without another general + /// sort specialization in the embedded binary. Existing ids move nothing. + fn insert(&mut self, eid: u64) -> Option { + let at = match self.ids.get(..self.len)?.binary_search(&eid) { + Ok(_) => return Some(true), + Err(at) => at, + }; + if self.len == BATCH_ROWS { + return Some(false); } - self.len = count; - Some(()) + let ids = self.ids.get_mut(..=self.len)?; + ids.copy_within(at..self.len, at + 1); + *ids.get_mut(at)? = eid; + self.len += 1; + Some(true) } fn get(&self, eid: u64) -> Option { @@ -354,7 +332,7 @@ mod tests { } #[test] - fn repeated_ids_do_not_sort_a_nearly_full_buffer_for_each_cell() { + fn repeated_ids_reuse_a_nearly_full_hint_buffer() { let mut keys = Keys::new(false); keys.limit = u64::try_from(BATCH_ROWS).unwrap(); let mut batch = Batch::new(2); @@ -363,11 +341,39 @@ mod tests { let f = u64::try_from((2 * i + 2).min(BATCH_ROWS - 1)).unwrap(); batch.push(&mut [Some(Cell::Eid(e)), Some(Cell::Eid(f))]); } - HINT_SORTS.with(|n| n.set(0)); let rows = project_with(&keys, &batch, &[0, 1], usize::MAX).unwrap(); assert_eq!(rows.len(), BATCH_ROWS); assert_eq!(keys.scalar.load(Ordering::Relaxed), 0); - HINT_SORTS.with(|n| assert!(n.get() <= 3, "repeats should reuse the sorted prefix")); + assert_eq!(keys.bulk.load(Ordering::Relaxed), 1); + } + + #[test] + fn sorted_hint_buffer_matches_a_set_at_every_capacity_boundary() { + use std::collections::BTreeSet; + let n = u64::try_from(BATCH_ROWS).unwrap(); + for input in [ + (1..=n + 1).collect::>(), + (1..=n + 1).rev().collect(), + (0..3 * n).map(|i| 1 + (i * 7919) % (n + 1)).collect(), + ] { + let mut hints = Uuids { + ids: [0; BATCH_ROWS], + values: [uuid::Uuid::nil(); BATCH_ROWS], + len: 0, + }; + let mut expected = BTreeSet::new(); + for eid in input { + let fits = expected.len() < BATCH_ROWS || expected.contains(&eid); + assert_eq!(hints.insert(eid), Some(fits)); + if fits { + expected.insert(eid); + } + assert_eq!( + hints.ids.get(..hints.len).unwrap(), + expected.iter().copied().collect::>() + ); + } + } } #[test] diff --git a/src/storage/btree.rs b/src/storage/btree.rs index 1fcc05272..d13549294 100644 --- a/src/storage/btree.rs +++ b/src/storage/btree.rs @@ -862,71 +862,6 @@ pub fn get( ) } -/// Exact lookups of sorted, distinct keys, visited in key order. -pub(crate) fn get_many>( - root: u64, - keys: &[K], - backend: &dyn StorageBackend, - cache: &PageCache, - visit: &mut impl FnMut(&K, Option>) -> Result<()>, -) -> Result<()> { - if keys - .iter() - .zip(keys.iter().skip(1)) - .any(|(a, b)| a.as_ref() >= b.as_ref()) - { - bail_coded!(ErrorCode::Int049, "lookup keys not sorted and distinct"); - } - get_many_at(root, keys, backend, cache, visit, 0) -} - -fn get_many_at>( - root: u64, - mut keys: &[K], - backend: &dyn StorageBackend, - cache: &PageCache, - visit: &mut impl FnMut(&K, Option>) -> Result<()>, - depth: usize, -) -> Result<()> { - if keys.is_empty() { - return Ok(()); - } - if depth == MAX_TREE_DEPTH { - bail_coded!( - ErrorCode::Int049, - format!("tree deeper than {MAX_TREE_DEPTH} below page_id={root}") - ); - } - let page = cache.get_or_load(root, backend)?; - match page.first().copied() { - Some(PAGE_TYPE_LEAF) => { - for key in keys { - visit(key, leaf_get(&page, key.as_ref())?)?; - } - } - Some(PAGE_TYPE_INTERNAL) => { - let node = Internal::new(&page)?; - while let Some(first) = keys.first() { - let child = node.route(first.as_ref(), 0)?; - let end = if child == node.count() { - keys.len() - } else { - let sep = node.sep(child)?; - keys.partition_point(|k| k.as_ref() < sep) - }; - if end == 0 { - bail_coded!(ErrorCode::Int049, "lookup child does not cover its key"); - } - let (group, rest) = keys.split_at(end); - get_many_at(node.child(child)?, group, backend, cache, visit, depth + 1)?; - keys = rest; - } - } - _ => bail_coded!(ErrorCode::Stg013, root), - } - Ok(()) -} - /// Every entry of the tree, in key order. #[cfg(test)] pub fn stream_all_entries( @@ -988,7 +923,7 @@ impl StorageBackend for MutexStorageBackend { } #[cfg(test)] -mod tests { +pub(crate) mod tests { use super::*; use crate::storage::backend::MemoryBackend; use crate::storage::keys::{Index, KeyFact, KeyValue}; @@ -1455,16 +1390,22 @@ mod tests { // ─── LeafCursor ────────────────────────────────────────────────────────── /// `MemoryBackend` that counts `read_page` calls, for seek cost tests. - struct CountingBackend { + pub(crate) struct CountingBackend { inner: MemoryBackend, reads: std::sync::atomic::AtomicU64, } impl CountingBackend { - fn reads(&self) -> u64 { + pub(crate) fn new() -> Self { + Self { + inner: MemoryBackend::new(), + reads: std::sync::atomic::AtomicU64::new(0), + } + } + pub(crate) fn reads(&self) -> u64 { self.reads.load(std::sync::atomic::Ordering::Relaxed) } - fn reset(&self) { + pub(crate) fn reset(&self) { self.reads.store(0, std::sync::atomic::Ordering::Relaxed); } } @@ -1492,91 +1433,6 @@ mod tests { } } - #[test] - fn get_many_shares_paths_without_reading_unrequested_leaves() { - let mut backend = CountingBackend { - inner: MemoryBackend::new(), - reads: std::sync::atomic::AtomicU64::new(0), - }; - let cache = PageCache::new(0); - let (root, _) = build_at(even_entries(20_000), &mut backend, &cache, 2); - for (step, dense) in [(1, true), (137, false)] { - let requested: Vec<_> = (0..1024).map(|i| key_for(i * step)).collect(); - backend.reset(); - let expected: Vec<_> = requested - .iter() - .map(|k| get(root, k, &backend, &cache).unwrap()) - .collect(); - let scalar_reads = backend.reads(); - backend.reset(); - let mut actual = Vec::new(); - get_many(root, &requested, &backend, &cache, &mut |_, v| { - actual.push(v); - Ok(()) - }) - .unwrap(); - assert_eq!(actual, expected, "same hits and misses in key order"); - assert!(backend.reads() <= scalar_reads, "sparse reads do not grow"); - if dense { - assert!( - backend.reads() < scalar_reads / 4, - "dense reads share paths" - ); - } - } - } - - #[test] - fn get_many_checks_input_and_stops_on_callback_error() { - let mut backend = CountingBackend { - inner: MemoryBackend::new(), - reads: std::sync::atomic::AtomicU64::new(0), - }; - let cache = PageCache::new(0); - let (root, _) = build_at(even_entries(100), &mut backend, &cache, 2); - backend.reset(); - get_many::>(root, &[], &backend, &cache, &mut |_, _| { - panic!("empty input must not visit"); - }) - .unwrap(); - assert_eq!(backend.reads(), 0); - for requested in [vec![key_for(2), key_for(1)], vec![key_for(1); 2]] { - let error = get_many(root, &requested, &backend, &cache, &mut |_, _| { - panic!("invalid input must not visit"); - }) - .unwrap_err(); - assert_eq!(crate::MinigrafError::from(error).code(), "INT-049"); - } - assert_eq!(backend.reads(), 0, "invalid input must not read"); - let mut visits = 0; - assert!( - get_many( - root, - &[key_for(0), key_for(2)], - &backend, - &cache, - &mut |_, _| { - visits += 1; - anyhow::bail!("visitor failed") - } - ) - .is_err() - ); - assert_eq!(visits, 1); - } - - #[test] - fn get_many_refuses_a_cycle() { - let (mut backend, cache, root, _) = multi_leaf_tree(); - let count = Internal::new(&cache.get_or_load(root, &backend).unwrap()) - .unwrap() - .count(); - redirect_child(&mut backend, &cache, root, count, root); - let error = - get_many(root, &[vec![255; 32]], &backend, &cache, &mut |_, _| Ok(())).unwrap_err(); - assert_eq!(crate::MinigrafError::from(error).code(), "INT-049"); - } - /// Entities `0, 2, 4, ...` so every odd entity is absent. fn even_entries(n: u64) -> Vec { (0..n).map(|i| entry(i * 2, 1)).collect() diff --git a/src/storage/dict.rs b/src/storage/dict.rs index 3974b96f0..282e4d0ef 100644 --- a/src/storage/dict.rs +++ b/src/storage/dict.rs @@ -36,6 +36,12 @@ pub(crate) fn check_eids(eids: &[u64]) -> Result<()> { Ok(()) } +fn decode_uuid(eid: u64, bytes: Option<&[u8]>) -> Result { + let bytes = bytes.ok_or_else(|| err_coded!(ErrorCode::Stg036, format!("entity id {eid}")))?; + Uuid::from_slice(bytes) + .map_err(|_| err_coded!(ErrorCode::Stg036, format!("entity id {eid}: bad UUID"))) +} + /// Ident and transaction lookups shared by every read of one committed meta. /// They never change once committed, and there are few of them compared with /// entities, so they are cached across reads; each map is cleared when it @@ -173,17 +179,18 @@ impl<'a> DictReader<'a> { if let Some(u) = self.uuids.get(&eid) { return Ok(*u); } - let v = self - .get(&keys::dict_eid_key(eid))? - .ok_or_else(|| err_coded!(ErrorCode::Stg036, format!("entity id {eid}")))?; - let u = Uuid::from_slice(&v) - .map_err(|_| err_coded!(ErrorCode::Stg036, format!("entity id {eid}: bad UUID")))?; + let u = self.read_uuid(eid)?; self.uuids.insert(eid, u); Ok(u) } - /// Resolve only the requested ids, sharing each visited DICT tree path. - /// Neither this reader's maps nor a query's metered maps are populated. + fn read_uuid(&self, eid: u64) -> Result { + let bytes = self.get(&keys::dict_eid_key(eid))?; + decode_uuid(eid, bytes.as_deref()) + } + + /// Dense chunks walk existing DICT leaves once; sparse/small chunks retain + /// scalar exact-key reads. Neither path populates an ephemeral UUID map. pub(crate) fn uuids_of( &self, eids: &[u64], @@ -194,37 +201,43 @@ impl<'a> DictReader<'a> { return Ok(()); } if self.root == 0 { - bail_coded!( - ErrorCode::Stg036, - format!("entity id {}", eids.first().copied().unwrap_or(0)) - ); + return decode_uuid(eids.first().copied().unwrap_or(0), None).map(|_| ()); } - // Stack storage bounds temporary memory even for callers larger than - // one engine batch. No per-key allocations or ephemeral UUID map. - let mut encoded = [keys::EidKey::default(); 1024]; - for chunk in eids.chunks(encoded.len()) { - for (dst, &eid) in encoded.iter_mut().zip(chunk) { - *dst = keys::EidKey::new(eid); + for chunk in eids.chunks(1024) { + let first = chunk.first().copied().unwrap_or(0); + let last = chunk.last().copied().unwrap_or(first); + let span_limit = u64::try_from(chunk.len()) + .unwrap_or(u64::MAX) + .saturating_mul(2); + if chunk.len() < 64 || last.saturating_sub(first) > span_limit { + for &eid in chunk { + visit(eid, self.read_uuid(eid)?)?; + } + continue; + } + let start = keys::dict_eid_key(first); + let mut cursor = + btree::LeafCursor::new(self.root, Some(&start), self.backend, self.cache)?; + for &eid in chunk { + let mut matched = false; + while let Some((key, bytes)) = cursor.next_ref()? { + let Some(rest) = key.strip_prefix(&[keys::DICT_EID_TO_UUID]) else { + break; + }; + let found = keys::read_uint_bytes(rest)?; + if found < eid { + continue; + } + if found == eid { + visit(eid, decode_uuid(eid, Some(bytes))?)?; + matched = true; + } + break; + } + if !matched { + return decode_uuid(eid, None).map(|_| ()); + } } - let mut ids = chunk.iter(); - btree::get_many( - self.root, - encoded.get(..chunk.len()).unwrap_or(&[]), - self.backend, - self.cache, - &mut |_, value| { - let eid = ids - .next() - .copied() - .ok_or_else(|| err_coded!(ErrorCode::Int049, "too many UUID lookups"))?; - let value = value - .ok_or_else(|| err_coded!(ErrorCode::Stg036, format!("entity id {eid}")))?; - let uuid = Uuid::from_slice(&value).map_err(|_| { - err_coded!(ErrorCode::Stg036, format!("entity id {eid}: bad UUID")) - })?; - visit(eid, uuid) - }, - )?; } Ok(()) } @@ -641,18 +654,24 @@ mod tests { .map(|e| { ( keys::dict_eid_key(e), - Uuid::from_u128(u128::from(e)).as_bytes().to_vec(), + if e == 1250 { + vec![0] + } else { + Uuid::from_u128(u128::from(e)).as_bytes().to_vec() + }, ) }) .collect(); // A damaged value must only fail when it is actually requested. entries.push((keys::dict_eid_key(2501), vec![0])); let mut alloc = PageAllocator::new(Vec::new(), 2, 1); + entries.push((keys::dict_ident_key(":after"), vec![0])); + entries.sort_by(|a, b| a.0.cmp(&b.0)); let root = btree::build_btree(entries, &mut backend, &cache, &mut alloc).unwrap(); let dict = DictReader::new(root, &backend, &cache); for requested in [ Vec::new(), - (1..=2500).collect(), + (1..=2500).filter(|&e| e != 1250).collect(), vec![1, 255, 256, 2048, 2500], ] { let mut actual = Vec::new(); @@ -668,7 +687,16 @@ mod tests { .collect(); assert!(actual == expected, "same UUIDs in requested order"); } - for requested in [vec![2501], vec![3000], vec![2, 1], vec![1, 1]] { + for requested in [ + vec![1250], + vec![2501], + vec![3000], + vec![2, 1], + vec![1, 1], + (0..64).collect(), + (2440..2504).collect(), + (3000..3064).collect(), + ] { let error = dict.uuids_of(&requested, &mut |_, _| Ok(())).unwrap_err(); let code = crate::MinigrafError::from(error).code(); assert_eq!( @@ -689,6 +717,59 @@ mod tests { ); } + #[test] + fn uuid_batches_preserve_partial_callback_errors_and_tree_errors() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(0); + let entries = (1..=4096u64) + .map(|e| { + ( + keys::dict_eid_key(e), + Uuid::from_u128(u128::from(e)).as_bytes().to_vec(), + ) + }) + .collect(); + let mut alloc = PageAllocator::new(Vec::new(), 2, 1); + let root = btree::build_btree(entries, &mut backend, &cache, &mut alloc).unwrap(); + let ids: Vec<_> = (1..=128).collect(); + let dict = DictReader::new(root, &backend, &cache); + let mut visits = 0; + assert!( + dict.uuids_of(&ids, &mut |_, _| { + visits += 1; + anyhow::bail!("visitor failed") + }) + .is_err() + ); + assert_eq!(visits, 1); + assert!(dict.uuids.is_empty(), "no speculative memo entries"); + let beyond: Vec<_> = (5000..5064).collect(); + assert_eq!( + crate::MinigrafError::from(dict.uuids_of(&beyond, &mut |_, _| Ok(())).unwrap_err()) + .code(), + "STG-036", + "end of eid tree" + ); + let original = backend.read_page(root).unwrap(); + for cycle in [false, true] { + let mut page = original.clone(); + if cycle { + let offset = crate::storage::node::RIGHTMOST_CHILD_OFFSET; + page[offset..offset + 8].copy_from_slice(&root.to_le_bytes()); + } else { + page[0] = crate::storage::page::PAGE_TYPE_VALUE; + } + crate::storage::page::seal(&mut page, root, 1).unwrap(); + backend.write_page(root, &page).unwrap(); + let dict = DictReader::new(root, &backend, &cache); + let error = dict.uuids_of(&beyond, &mut |_, _| Ok(())).unwrap_err(); + assert_eq!( + crate::MinigrafError::from(error).code(), + if cycle { "INT-049" } else { "STG-013" } + ); + } + } + /// Encode `facts` on top of the dictionary at `root`, write the new DICT /// tree, and return `(new_root, encoded)`. fn checkpoint( diff --git a/src/storage/keys.rs b/src/storage/keys.rs index 0aed5f09d..483adbe07 100644 --- a/src/storage/keys.rs +++ b/src/storage/keys.rs @@ -822,39 +822,9 @@ pub fn dict_uuid_key(uuid: &Uuid) -> Vec { } pub fn dict_eid_key(eid: u64) -> Vec { - EidKey::new(eid).as_ref().to_vec() -} - -/// A DICT entity key without an allocation, for bounded lookup batches. -#[derive(Clone, Copy, Default)] -pub(crate) struct EidKey { - bytes: [u8; 10], - len: u8, -} - -impl EidKey { - pub(crate) fn new(eid: u64) -> Self { - let (bytes, skip) = magnitude_bytes(eid); - let tail = bytes.get(skip..).unwrap_or(&[]); - let n = u8::try_from(tail.len()).unwrap_or(8); - let mut key = Self { - bytes: [0; 10], - len: 2 + n, - }; - for (dst, src) in key.bytes.iter_mut().zip([DICT_EID_TO_UUID, INT_ZERO + n]) { - *dst = src; - } - for (dst, src) in key.bytes.iter_mut().skip(2).zip(tail) { - *dst = *src; - } - key - } -} - -impl AsRef<[u8]> for EidKey { - fn as_ref(&self) -> &[u8] { - self.bytes.get(..usize::from(self.len)).unwrap_or(&[]) - } + let mut k = vec![DICT_EID_TO_UUID]; + put_uint(&mut k, eid); + k } pub fn dict_ident_key(ident: &str) -> Vec { @@ -1512,28 +1482,6 @@ mod tests { ); } - #[test] - fn fixed_eid_keys_match_dictionary_encoding_and_order() { - let mut ids = vec![0, 1]; - for bytes in 1..8 { - let boundary = 1u64 << (bytes * 8); - ids.extend([boundary - 1, boundary]); - } - ids.push(u64::MAX); - let mut previous = Vec::new(); - for eid in ids { - let fixed = EidKey::new(eid); - let mut expected = vec![DICT_EID_TO_UUID]; - put_uint(&mut expected, eid); - assert_eq!(fixed.as_ref(), expected); - assert!( - previous.as_slice() < fixed.as_ref(), - "ids retain byte order" - ); - previous = fixed.as_ref().to_vec(); - } - } - #[test] fn malformed_keys_are_int_049() { for bad in [&[][..], &[0x30][..], &[0x15][..], &[TAG_STRING, b'a'][..]] { diff --git a/src/storage/mod.rs b/src/storage/mod.rs index e97329763..88e3cb327 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -519,18 +519,13 @@ pub trait KeySource: Send + Sync { /// Visit the UUIDs of strictly increasing, distinct committed entity ids. /// Uses this reader's pinned generation, just as [`Self::uuid_of`] does. /// An empty slice reads nothing; invalid ordering is `INT-049`. - /// The default performs scalar lookups; on-disk readers share tree paths. + /// On-disk readers share tree paths. + /// On error, `visit` may have received a prefix; discard partial hints. fn uuids_of( &self, eids: &[u64], visit: &mut dyn FnMut(u64, crate::graph::types::EntityId) -> Result<()>, - ) -> Result<()> { - dict::check_eids(eids)?; - for &eid in eids { - visit(eid, self.uuid_of(eid)?)?; - } - Ok(()) - } + ) -> Result<()>; /// The ident with id `iid`. fn ident_of(&self, iid: u32) -> Result; /// The long string stored at `vref`. diff --git a/src/storage/reader.rs b/src/storage/reader.rs index 467486bad..5abbaf9d8 100644 --- a/src/storage/reader.rs +++ b/src/storage/reader.rs @@ -591,43 +591,12 @@ pub fn all_entries_as_facts( #[cfg(test)] mod uuid_batch_tests { use super::*; - use crate::storage::backend::MemoryBackend; + use crate::storage::btree::tests::CountingBackend; use crate::storage::page::PageAllocator; - use std::sync::atomic::{AtomicUsize, Ordering}; - - struct CountReads { - inner: MemoryBackend, - reads: AtomicUsize, - } - - impl StorageBackend for CountReads { - fn write_page(&mut self, id: u64, bytes: &[u8]) -> Result<()> { - self.inner.write_page(id, bytes) - } - fn read_page(&self, id: u64) -> Result> { - self.reads.fetch_add(1, Ordering::Relaxed); - self.inner.read_page(id) - } - fn sync(&mut self) -> Result<()> { - self.inner.sync() - } - fn page_count(&self) -> Result { - self.inner.page_count() - } - fn close(&mut self) -> Result<()> { - self.inner.close() - } - fn backend_name(&self) -> &'static str { - "counted memory" - } - } #[test] fn on_disk_uuid_override_shares_paths() { - let mut backend = CountReads { - inner: MemoryBackend::new(), - reads: AtomicUsize::new(0), - }; + let mut backend = CountingBackend::new(); let cache = Arc::new(PageCache::new(0)); let entries = (1..=2048u64) .map(|e| { @@ -644,20 +613,41 @@ mod uuid_batch_tests { meta.next_eid = 2049; let backend = Arc::new(Mutex::new(backend)); let reader = OnDiskReader::new(backend.clone(), cache, &meta); - let requested: Vec<_> = (1..=2048).collect(); - backend.lock().unwrap().reads.store(0, Ordering::Relaxed); - let mut seen = 0; - reader - .uuids_of(&requested, &mut |e, u| { - assert!(u == EntityId::from_u128(u128::from(e)), "same UUID"); - seen += 1; - Ok(()) - }) - .unwrap(); - assert_eq!(seen, requested.len()); - assert!( - backend.lock().unwrap().reads.load(Ordering::Relaxed) < requested.len() / 4, - "on-disk override must share paths rather than use the scalar default" - ); + let cases = [ + ((1..=2048).collect::>(), true), + ((1..=63).collect(), false), + ((1..=64).collect(), true), + ((1..=256).map(|i| i * 7).collect(), false), + ((1..=63).chain([129]).collect(), true), + ((1..=63).chain([130]).collect(), false), + ]; + for (requested, dense) in cases { + backend.lock().unwrap().reset(); + let expected: Vec<_> = requested + .iter() + .map(|&e| reader.uuid_of(e).unwrap()) + .collect(); + let scalar_reads = backend.lock().unwrap().reads(); + backend.lock().unwrap().reset(); + let mut actual = Vec::new(); + reader + .uuids_of(&requested, &mut |_, u| { + actual.push(u); + Ok(()) + }) + .unwrap(); + assert!(actual == expected, "same UUIDs in requested order"); + let batch_reads = backend.lock().unwrap().reads(); + assert!( + batch_reads <= scalar_reads, + "sparse batches retain scalar read cost" + ); + if dense { + assert!( + batch_reads < scalar_reads / 4, + "dense batches share leaf reads" + ); + } + } } }