diff --git a/CHANGELOG.md b/CHANGELOG.md index 1fa8a50851..62915cb02c 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -55,6 +55,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **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. - **`BrowserDb` binds sets** (#316). A prepared query's binding can be a set: `{ type: 'set', value: [1, 2] }` or a JS `Set`. Elements are plain values or typed value forms (`{ type: 'keyword', value: ':k' }`); an element that is an entity, tx count, timestamp or any-valid-time form is `API-017`, a set inside a set `API-021`. Any other element, and a plain array as a binding, is a `TypeError`, as for any value that is no bind value. +- **Set values in every binding** (#316). Python, Java, Android and Swift return a set value as `MiniGrafValue.Set` (its elements in canonical order) in fact records and take it in bind values and the log writer; Node.js and C as `{"type": "set", "value": [...]}`. Each binding's native set binds a set value: a Python `set`/`frozenset`, a Kotlin/Java `Set`, a Swift `Set` of `MinigrafSetElement`s, a JS `Set` in Node.js and the browser; a UUID element is a ref. A set inside a set is `API-021`. `execute()` returns a set as a JSON array, in every binding. - **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 ?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`. diff --git a/ROADMAP.md b/ROADMAP.md index d19644aafa..037b701b8c 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -102,7 +102,7 @@ Scope — query API: Scope — features: - Query profiler (#185) -- Set membership predicates (#316) +- Set values `#{...}`, the set predicates `in?`/`not-in?`/`any-in?`/`all-in?`/`none-in?` and `collect-set` (#316; done on `v3`: core, `BrowserDb` set binds, and set values in Python, Java, Android, Swift, Node.js, C and the browser/WASI packages on their `v3` branches) - Prepared queries in every binding (#181; done on `v3`: core, `BrowserDb.prepare`, and Python, Java, Android, Swift, Node.js and C on their `v3` branches) - UDF registration in every binding: the UniFFI ones, C, Node and the browser `BrowserDb` (#180) - `OpenOptions` exposed over UniFFI through `open_with_options`, so embedders can suppress the close-time checkpoint (#322; done on `v3` in every binding with #465)