adityamukho · Oct 24, 2026 · Oct 24, 2026 · Oct 24, 2026 · Oct 24, 2026 · Oct 24, 2026
@@ -53,6 +53,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 
 - **Set values: `#{...}`** (#316, PR 1 of 3). A fact's value can be a finite set of scalars, `[:alice :user/scopes #{:scope/read :scope/write}]`, written in query text, returned as `Value::Set(ValueSet)`, transacted, retracted and queried by exact value (`[?e :user/scopes #{:scope/write :scope/read}]`), joined on and grouped by. Duplicates are removed and element order does not matter. Two elements are the same when `Value`'s order says so: `0.0` and `-0.0` are one element (`-0.0` is kept), every NaN is one element, a keyword never equals a ref and `1` never equals `1.0`. A set cannot hold a set (`ValueSet::new` fails with the new `API-021`; in query text, `PRS-119`); its elements are literals only (`PRS-120`), and an unclosed `#{` is `PRS-121`. In format v8 a set has value tag `0x08`, after refs; a set whose encoded elements take at most 64 bytes is stored in its index keys, a longer one once in a value page, as a long string is. On a file database a stored set may take up to 4,068 bytes, counting each keyword element as 6 bytes and each ref as 10 (`WAL-003`). The REPL prints sets as `#{...}` and `BrowserDb` returns them as JSON arrays, in `Value`'s order.
 - **Set-membership predicates** (#316, PR 2 of 3). `[(in? ?role #{:role/admin :role/owner})]` keeps rows whose value is in a set, and `not-in?`, `any-in?` (the two sets share an element), `all-in?` (every element of the first is in the second) and `none-in?` (they share none) complete the five. Each works as a filter or binds a Boolean, `[(any-in? ?scopes #{:scope/write}) ?can-write]`, and takes literal sets, set-valued attributes and bind slots (`BindValue::Val(Value::Set(..))`). Membership is set equality, as for set values: `0.0` is in `#{-0.0}`, NaN is in a set holding NaN, a keyword is not a ref. `in?` of an empty set is false and `not-in?` true; `all-in?` and `none-in?` of an empty first set are true and `any-in?` false. A set where a scalar is needed, or a scalar where a set is needed, is a type mismatch: the filter drops the row and the binding binds nothing, so `not-in?` with a non-set is never true. `contains?` stays string-only. The five names cannot be registered as functions.
+- **`collect-set`** (#316, PR 3 of 3). `[(collect-set ?e :user/scope) ?scopes]` binds, per row, the set of the values of `[?e :user/scope ?v]` under the query's `:as-of` and `:valid-at`, with retractions applied as for that pattern, and `#{}` when there are none (the row is kept). Combine it with the set predicates: `[(collect-set ?e :user/scope) ?s] [(in? :scope/admin ?s)]`. `?e` must be bound by an earlier clause (`INT-018`); a keyword names its entity, and a value that is no entity gives `#{}`. It works in `:where`, rule bodies, `not-join` bodies and `or` branches; when its output variable is already bound, it keeps the rows where the two sets are equal. It reads stored facts only, never a rule's derived facts. New codes: `PRS-122` (no output variable), `PRS-123` (an operand that is not a `?variable` then an attribute keyword, a bind slot included) and `QRY-015` (a value found is itself a set: bind a set-valued attribute with a pattern). The set it builds counts toward `query_memory_limit` (`QRY-012`). `collect-set` is read only as a whole clause (`PRS-067` inside another expression) and cannot be registered as a function.
 - **Every query runs on a streaming engine** (#473: #544, #545, #546, #547, #548, #549, #551). The executor, which turned every live fact of each pattern's attribute into a `Fact` before matching, held each row's bindings in a map and copied the database into a `FactStorage` for every rule query, no longer runs queries: its query path, `PatternMatcher` and the old rule evaluators are gone (#551), and the release binary is 1,153 KiB instead of 1,286 KiB (CI's size check). A query is now a tree of operators that pass batches of up to 1,024 rows of ids, read from the index keys, and turn ids into values only for the rows they return (#530). A pattern reads the narrowest key range its constants allow (`[?e :a C]` reads the AVET range of `C`, #518); a later pattern is an `IndexNestedLoopJoin` when its entity is bound and a `HashJoin` otherwise, built on the side with the smaller estimate (with no shared variable, the smaller product, #575); per-fact pseudo-attributes read their source's metadata column (#594). `not` / `not-join` is an `AntiJoin` and `or` / `or-join` a `Union` and `Distinct`: a body or branch with the same rows for every outer row runs once into a hash table, any other runs per outer row from a one-row seed. Aggregates keep one entry per group (one set of accumulators when ungrouped), windows hold their rows, and rule queries derive each stratum's relations semi-naively, with the magic-set rewrite, then read them as patterns. `:as-of` with a time bounds the transaction counter when transaction times rise with it, and otherwise keeps the versions of transactions at or before the time. Cursors (`Minigraf::query`, `PreparedQuery::query`, `BrowserDb.query`) pull one batch at a time, and closing or dropping one stops the work; a cursor still answers from the database as it was when it opened. Every operator that keeps state counts it against `OpenOptions::query_memory_limit` (#549, below). Answers are the executor's, as a bag, except for the changes under Breaking changes: until #551 every query in the test suite was also run by the executor and the answers had to agree, and the answers of the suites that relied on that are recorded in `tests/answers/`. Measured with the #394 envelope at 1M facts, executor → engine, p50 and peak RSS (`docs/BENCHMARKS.md` has every shape at 100K, 1M and 10M): `[?e :name "…"]` 288 ms → 22 µs; an attribute scan of 166,666 rows drained with `next_batch(1000)` 58 → 7 MiB (458 → 7 MiB at 10M); `[:p :follows ?f] [?f :name ?n]` 796 ms → 50 µs; an entity-bound `not` 760 → 27 ms; `[:find (count ?v) :where [?e ?a ?v]]` 3.01 s → 457 ms and 728 → 7 MiB (6.6 GiB → 7 MiB at 10M); an `or-join` of two hashed branches 1.44 s → 80 ms; `(boss :p<leaf> ?b)` 43.9 s → 2.14 ms and 2.6 GiB → 4 MiB; the whole transitive closure of `:manager` 51.0 s → 3.21 s and 4.7 GiB → 318 MiB; `:as-of` with a time, a point query, 1.65 s → 0.8 ms and 435 → 4 MiB (17.2 s and 3.6 GiB → 0.9 ms and 5 MiB at 10M).
 - **Transactions of any size on a file database, in bounded memory** (#473, part 8: #550). `transact` and `retract` are read one fact at a time: the whole command is never tokenized, parsed or materialised at once, and a statement reports the same error code as before whatever its size. A transaction becomes *large* when its facts would pass the new `OpenOptions::transaction_chunk_facts` (default 65,536, kept between 1 and 1,000,000): `Minigraf::execute` of a larger statement, or the `WriteTransaction` statement that takes its staged facts past it. A large transaction holds at most one chunk of facts in memory. It writes them a chunk at a time into copy-on-write trees that become the next generation, and commits as a checkpoint: no WAL entry, and the uncheckpointed facts of earlier transactions go into the same checkpoint. What a large transaction stores is what a small one stores, with two differences you can see: its `tx_id` is the time it became large, not its commit time (a default `:valid-from` takes that time too), and errors from different chunks of one statement come in chunk order. In a large `WriteTransaction` a rejected statement still leaves the transaction usable and the earlier statements' facts as they were; a fact too large to store is rejected at its statement (`WAL-003`) rather than at `commit`; a handle that has failed is refused when the transaction becomes large (`STG-046`) rather than at `commit`; and inside the transaction `:as-of` its own transaction number sees every finished statement, since they share one number (staged statements of a small transaction each have their own until `commit`). A crash at any point before a large transaction's commit leaves the database as it was; the WAL file exists, header only, from before its first page write, so a new file reopens too. The first checkpoint after a WAL is found at open, or after a large transaction is rolled back, now writes a meta page before it deletes the WAL. Measured at 1M facts against v3 before this change (one `execute`, or a `WriteTransaction` of 10 statements): peak memory above the input text goes from 1.3–2.4 GiB to at most 55 MiB at the default (under 10 MiB at 16,384); with sequential entities it is faster (3.9 s from 9.1 s for short values), with random entities about as fast for short values (9.5 s from 11.4 s in one `execute`) and slower for long ones over 10 statements (34 s from 22 s; 16,384 takes up to twice as long as the default with random entities), and a transaction of several statements over random entities can leave the file up to 1.8× larger, since each statement keeps the pages its base references until it ends; later checkpoints reuse that space.
 - **Queries inside a `WriteTransaction` read through a snapshot** (#550). They no longer copy every committed and pending fact into a new list: they read the committed indexes and the pending facts, with the transaction's staged facts read with the pending ones (or, in a large transaction, its working trees), and run on the streaming engine where it plans them, counted by `query_memory_limit`.

@@ -147,7 +147,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)
    - `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), `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`), `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), `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`; each entry charged by a per-entry estimate 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` /
984C
 `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`), `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), `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 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)
 
@@ -215,7 +215,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**1775 tests** (1762 passing, 13 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
+**1792 tests** (1779 passing, 13 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.