diff --git a/CHANGELOG.md b/CHANGELOG.md index 6bbf35a762..d0be46c623 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -46,7 +46,9 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Added -- **Query memory accounting and `OpenOptions::query_memory_limit`** (#549). Every engine operator that keeps state counts an estimate of the bytes it holds, per entry, the same on every platform: a hash join's build side, a negation's or an `or`'s table, a distinct set, an aggregate's groups (`count-distinct` and `sum-distinct` members included), a window's rows, the facts a rule query derives and the stored facts it compares them with, and the query's entity and ident ids. Tables grow through `try_reserve`. The new `OpenOptions::query_memory_limit` (default `usize::MAX`, off) turns a query that would hold more into the new `QRY-012`, which frees what the query held and leaves the database and other queries as they were; through a cursor, the rows already returned stay returned. An allocation the allocator refuses is `QRY-012` too, in place of the abort. Rows passing between operators and the answer `execute` collects are not counted; a query inside a write transaction that has staged writes is not counted yet (#551). +- **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`. +- **Query memory accounting and `OpenOptions::query_memory_limit`** (#549). Every engine operator that keeps state counts an estimate of the bytes it holds, per entry, the same on every platform: a hash join's build side, a negation's or an `or`'s table, a distinct set, an aggregate's groups (`count-distinct` and `sum-distinct` members included), a window's rows, the facts a rule query derives and the stored facts it compares them with, and the query's entity and ident ids. Tables grow through `try_reserve`. The new `OpenOptions::query_memory_limit` (default `usize::MAX`, off) turns a query that would hold more into the new `QRY-012`, which frees what the query held and leaves the database and other queries as they were; through a cursor, the rows already returned stay returned. An allocation the allocator refuses is `QRY-012` too, in place of the abort. Rows passing between operators and the answer `execute` collects are not counted, nor are a write transaction's staged facts (at most one chunk, #550). - **Binding support for cursors, open options, the fact log and the log writer** (#462, #465, #467). Two new codes let language bindings report what Rust's types rule out: `API-017` (an argument the binding cannot convert, such as an entity id that is not a UUID string), from `MinigrafError::invalid_argument`, and `API-018` (a log writer used after `finish` or `close`), from `MinigrafError::closed`. `BrowserDb.query(datalog)` returns a `BrowserCursor` with `vars()`, `nextBatch(maxRows)` (rows as JSON, as in `execute()`, or `undefined` at the end) and `close()`. The shared binding shape is in `docs/superpowers/specs/2026-10-07-binding-etl-surface-design.md`. The wasm32 test build compiles again (a duplicate `page_cache_capacity` and `tempfile` tests on wasm32). - **Fact log: `Minigraf::fact_log()`** (#430). Streams every fact version in the database as `FactRecord`s (entity, attribute, value, `tx_count`, `tx_id`, valid-time bounds, and whether it is an assertion or a retraction), without Datalog. `FactFilter` selects attributes (exact or by prefix), entities and a `tx_count` range, checked on index keys so excluded records are never decoded. `FactOrder::Tx` (the default) returns records in ascending `tx_count`; format v8 has no index in transaction order, so it holds at most `FactFilter::window` records (default 262,144) and scans the selected keys once per window. `FactOrder::Storage` reads in one pass. The log reads the database as it was when it opened. Writes, checkpoints and `rebuild_indexes()` go on while it is open (#543): the log pins the committed generation it opened on, and no checkpoint reuses a page that generation references, so the file grows by the pages checkpoints replace until the log is closed, dropped or read to the end; later checkpoints reuse them. `API-013` (checkpoint while a fact log is open), added with the fact log in earlier v3.0.0 development builds, is deprecated: no longer emitted, still registered, never reused. Like `Cursor`, a `FactLog` is owned and `Send`. Rust API only for now; the bindings follow. - **Raw log writer: `LogWriter`** (#431). Builds a new database from explicit `FactRecord`s, the load step of an offline migration after `fact_log()` on a read-only source. Each record keeps its `tx_count`, `tx_id`, valid-time window and assertion flag. Records come in transaction order, gaps allowed: leaving a transaction out leaves a hole, and `:as-of` on it shows the state before. `advance_tx_count` keeps the source's counter after trailing purged transactions. The checks are structural only: order (new `API-015`), one `tx_id` per transaction (new `API-016`) and size (`WAL-003`); a rejected record changes nothing. Every file it builds keeps the rules of a normal write (#436, #477): a valid-time window that ends at or before it starts is `API-019`, a second window of one fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction the new `API-020`. An unfiltered copy of a source that keeps these rules is identical to it. A source written before them (v2.x, or earlier v3 builds) can break them, and copying it fails at the first such record, so a middleware step must repair those records first; `docs/ERROR_REFERENCE.md` describes each repair. There is no WAL: records are committed in batches with the normal copy-on-write checkpoint, never splitting a transaction. The file is built at `.partial` and renamed into place by `finish`, so a crash or an abandoned build never leaves part of a log at `path`; an existing target or WAL is the new `STG-043`. The page-range copy the issue proposed is not provided, since v8 pages share one dictionary and are not self-contained. The bindings follow. @@ -92,7 +94,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Internal -- **Single-pattern queries run on a new streaming engine** (#473, part 2: #544, first PR). A query whose `:where` is one pattern and whose `:find` holds plain variables now runs on operators that read index keys in batches of 1,024 rows and turn ids into values only for the rows they return (#530, for these queries). A pattern with a constant attribute and value, `[?e :a C]`, reads the AVET range of `C` instead of every fact of the attribute (#518). Measured at 1M facts (#394 envelope, `[?e :name "…"]`): 344 ms → 20 µs and 142 → 3 MiB; an attribute scan of 166,666 rows 577 → 268 ms and 172 → 57 MiB; point and `:as-of` queries 10–30 % faster. Every other query, and reads inside a `WriteTransaction`, run on the existing executor as before. Results are unchanged: in tests, every query the engine runs is also run by the executor and the answers must agree, and CI runs the whole suite that way (`test-oracle` feature). +- **Single-pattern queries run on a new streaming engine** (#473, part 2: #544, first PR). A query whose `:where` is one pattern and whose `:find` holds plain variables now runs on operators that read index keys in batches of 1,024 rows and turn ids into values only for the rows they return (#530, for these queries). A pattern with a constant attribute and value, `[?e :a C]`, reads the AVET range of `C` instead of every fact of the attribute (#518). Measured at 1M facts (#394 envelope, `[?e :name "…"]`): 344 ms → 20 µs and 142 → 3 MiB; an attribute scan of 166,666 rows 577 → 268 ms and 172 → 57 MiB; point and `:as-of` queries 10–30 % faster. Every other query runs on the existing executor as before. Results are unchanged: in tests, every query the engine runs is also run by the executor and the answers must agree, and CI runs the whole suite that way (`test-oracle` feature). - **Expressions and pseudo-attributes run on the streaming engine** (#473, part 2: #544, second PR). The engine now also runs expression clauses after its pattern (`[(> ?v 21)]`, `[(+ ?v 1) ?w]`, registered predicates), per-fact pseudo-attribute patterns on the pattern's entity (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`), and keyword, UUID and float constants in the value position. A constant reads only the AVET ranges it can match: a keyword reads its own range and the range of refs to the entity it names, a UUID reads its ref range and the attribute's keywords, a float reads the attribute's floats. The executor's matching rules are kept (a keyword matches a ref to the entity it names, a UUID matches a keyword that names it, floats match within `f64::EPSILON`), and so are its errors (INT-026, QRY-007). `:db/valid-at`, which the executor matches against every fact of the entity, stays on the executor until joins (#545). - **Cursors stream the queries the engine runs** (#473, part 2: #544, third PR). `Minigraf::query`, `PreparedQuery::query` and `BrowserDb.query` no longer compute the whole answer at open for these queries: the cursor pulls one batch of up to 1,024 rows from the engine's operators when it runs out of rows, and `close` or dropping it stops the work. An attribute scan drained with `next_batch(1000)` holds 7 MiB at 1M and 10M facts (was 58 and 458 MiB) and runs 3–17 % faster (#394 envelope). The answer is still the database as it was when the cursor opened, whatever is written or checkpointed while it is open. A read error that happens after some rows of a `next_batch` call were gathered is returned by the next call, after those rows. No API change. - **Joins run on the streaming engine** (#473, part 3: #545, second PR). Queries of several patterns with stored attributes, with or without expression clauses, now run on the engine. Patterns run in the planner's order: the first is a scan, and each later one is an `IndexNestedLoopJoin` when its entity is a variable already bound (one entity range per row, committed and pending), or a `HashJoin` otherwise (value and attribute positions, cross products), built on the side with the smaller estimate. Joins follow the executor's rules (#545, first PR): floats are equal by IEEE `==`, a keyword equals a ref to the entity it names, and a variable keeps the value of its first pattern in the `:where` text. Measured at 1M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n]` 796 ms → 50 µs and 322 → 4 MiB; `[:p :manager ?b] [?s :manager ?b] [?s :name ?n]` 1.67 s → 148 ms and 392–462 → 14 MiB; `[?e :follows ?f] [?f :group 7] [?f :name ?n]` 2.6 s → 1.1 s and 468–480 → 42 MiB. `or`, `not`, rules and aggregates still run on the executor. Results are unchanged (`test-oracle`). @@ -100,7 +102,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **`not` and `not-join` run on the streaming engine** (#473, part 4: #546, first PR). An `AntiJoin` keeps the outer rows for which the body has no row; it never deduplicates. A body that has the same rows for every outer row (its expressions and pseudo-attributes read only variables its own patterns bind) runs once, and its rows' values of the variables it shares with the outer row form a hash set. Any other body, and one whose first pattern's entity comes from the outer row, runs once per outer row from a one-row seed of the values it imports, stopping at its first row: an entity-bound body costs one index probe per row and holds nothing. Bodies are ordered with the imported variables counted as bound. Queries whose negation holds a rule invocation stay on the executor. Measured (#394 envelope, p50 and peak RSS): an entity-bound `not` (`[?e :group 7] (not [?e :age 7])`, run per row) 760 ms → 27 ms and 222 → 6 MiB at 1M facts, 8.7 s → 0.29 s and 1.2 GiB → 6 MiB at 10M; a `not-join` keyed on a value whose body has an expression (`(not-join [?a] [?f :group 17] [?f :age ?a] [(< ?a 50)])`, hashed) 1.29 s → 5.8 ms at 100K, over 60 s → 53 ms and 171 → 7 MiB at 1M, over 60 s → 0.57 s and 1.5 GiB → 9 MiB at 10M. Other workloads unchanged. Results are unchanged (`test-oracle`). - **Aggregates run on the streaming engine** (#473, part 5: #547, second PR). Queries with aggregates in `:find`, with or without `:with`, now run on the engine when their `:where` does. An `Aggregate` operator keeps one entry per group in a hash table, keyed on the grouping cells as groups compare values, and steps each aggregate as rows arrive: a query with no grouping variable holds one set of accumulators, whatever the input size. `count` reads only whether a cell is `nil` and `count-distinct` keeps the keys of its cells, so neither turns ids into values; other aggregates read values. When the input ends, the groups are sorted by their values, finished in that order and returned in batches. Measured (#394 envelope, p50 and peak RSS): `[:find (count ?v) :where [?e ?a ?v]]` 207 ms → 44 ms and 97 → 7 MiB at 100K facts, 3.01 s → 457 ms and 728 → 7 MiB at 1M, 29.6 s → 4.46 s and 6.6 GiB → 7 MiB at 10M; `[:find ?g (count ?e) :where [?e :group ?g]]` 31 → 5.9 ms at 100K, 397 → 61 ms and 97 → 7 MiB at 1M, 4.51 s → 614 ms and 901 → 7 MiB at 10M. Other workloads unchanged. Results are unchanged apart from the float group value above (`test-oracle`). - **Window functions run on the streaming engine** (#473, part 5: #547, third PR). Queries with window functions in `:find`, alone or over an aggregate's groups, now run on the engine when their `:where` does. A `Window` operator holds each input row's returned cells and the values of the variables the windows read, then computes every window with the code the executor runs (partitions, the sort, peers) and returns the rows in input order. Measured (#394 envelope, p50 and peak RSS): `[:find ?e (rank :over (:order-by ?a)) :where [?e :age ?a]]` 41.5 → 32.8 ms and 19 → 16 MiB at 100K facts, 601 → 434 ms and 140 → 109 MiB at 1M, 7.89 s → 5.65 s and 1,257 → 1,030 MiB at 10M. A window holds every row by nature, so memory still grows with the input. Other workloads unchanged. Results are unchanged (`test-oracle`). -- **Rule queries run on the streaming engine** (#473, part 6: #548, second PR). A query that invokes a rule, at any depth, now runs on the engine when its body and the body of every rule it evaluates do. Each evaluated predicate has a relation: the facts its rules derive, held as rows of ids, a set (a fact derived twice, or equal to a stored fact, is kept once). `Recursive` derives the relations stratum by stratum before the body runs. Round 1 runs every rule over all facts; each later round runs a rule once per top-level invocation of its own stratum, that invocation reading only the facts the last round derived, so a fact is derived from new facts only (semi-naive). A rule that reads its own stratum otherwise (in an `or` branch, through a `[?x :p ?y]` or `[?x ?a ?v]` pattern, or `:db/valid-at`) runs over all facts every round. Scans read a relation's rows after the committed and pending facts, with `nil` metadata; entity probes use the relation's index. The query body is planned as any engine query, rule invocations read as patterns of their relations. The executor's `FactStorage` copy of the database for each rule query is gone on this path. Queries inside a write transaction, with an `:as-of` timestamp, or with a rule body the engine does not plan (an expression-only body, a nested `or`) stay on the executor. The binary-size gate on `v3` is 1,260 KiB until #551 removes the executor's query path (it was 1,230 KiB; this adds about 34 KiB). Measured (#394 envelope, executor → engine, p50 and peak RSS at 100K / 1M / 10M facts; `docs/BENCHMARKS.md`): `recursive_ancestors` (`(boss :p ?b)`, 5–7 ancestors through the magic-set rewrite) 2.71 s → 1.45 ms, 43.9 s → 2.14 ms, over 60 s → 3.04 ms, at 4 MiB instead of 253 MiB, 2.6 GiB and over 8.8 GiB; the whole transitive closure (`[:find ?x ?b :where (boss ?x ?b)]`, 72K, 889K and 10.6M derived facts) 3.04 s → 211 ms, 51.0 s → 3.21 s, over 60 s → 53.8 s, and 484 MiB → 45 MiB, 4.7 GiB → 318 MiB, over 8.8 GiB → 2.5 GiB. Other workloads unchanged. Results are unchanged (`test-oracle`). +- **Rule queries run on the streaming engine** (#473, part 6: #548, second PR). A query that invokes a rule, at any depth, now runs on the engine when its body and the body of every rule it evaluates do. Each evaluated predicate has a relation: the facts its rules derive, held as rows of ids, a set (a fact derived twice, or equal to a stored fact, is kept once). `Recursive` derives the relations stratum by stratum before the body runs. Round 1 runs every rule over all facts; each later round runs a rule once per top-level invocation of its own stratum, that invocation reading only the facts the last round derived, so a fact is derived from new facts only (semi-naive). A rule that reads its own stratum otherwise (in an `or` branch, through a `[?x :p ?y]` or `[?x ?a ?v]` pattern, or `:db/valid-at`) runs over all facts every round. Scans read a relation's rows after the committed and pending facts, with `nil` metadata; entity probes use the relation's index. The query body is planned as any engine query, rule invocations read as patterns of their relations. The executor's `FactStorage` copy of the database for each rule query is gone on this path. Queries with an `:as-of` timestamp, or with a rule body the engine does not plan (an expression-only body, a nested `or`) stay on the executor. The binary-size gate on `v3` is 1,260 KiB until #551 removes the executor's query path (it was 1,230 KiB; this adds about 34 KiB). Measured (#394 envelope, executor → engine, p50 and peak RSS at 100K / 1M / 10M facts; `docs/BENCHMARKS.md`): `recursive_ancestors` (`(boss :p ?b)`, 5–7 ancestors through the magic-set rewrite) 2.71 s → 1.45 ms, 43.9 s → 2.14 ms, over 60 s → 3.04 ms, at 4 MiB instead of 253 MiB, 2.6 GiB and over 8.8 GiB; the whole transitive closure (`[:find ?x ?b :where (boss ?x ?b)]`, 72K, 889K and 10.6M derived facts) 3.04 s → 211 ms, 51.0 s → 3.21 s, over 60 s → 53.8 s, and 484 MiB → 45 MiB, 4.7 GiB → 318 MiB, over 8.8 GiB → 2.5 GiB. Other workloads unchanged. Results are unchanged (`test-oracle`). - **`or` and `or-join` run on the streaming engine** (#473, part 4: #546, second PR). A `Union` extends each outer row by every row of every branch; a `Distinct` then keeps one of each set of equal rows, comparing values as the executor does (`0.0` equals `-0.0`, a keyword never equals a ref, a row holding NaN is never a duplicate). Each branch is planned as a `not` body is: a branch with the same rows for every outer row runs once, into a table of its rows by their values of the variables it shares with the outer row; any other branch, and one whose first pattern's entity comes from the outer row, runs per outer row from a one-row seed. When the branches bind no new variable (every `or-join`, and an `or` that only filters), an outer row is returned once, from the first branch that has a row. A query whose first clause to run is an `or` starts from the empty row. These stay on the executor: a branch with a rule invocation, a nested `or`, or a predicate the function registry may not have; an `or` whose branches bind their own patterns' metadata; and a branch whose `not` reads a variable only the branch's expression binds. Measured (#394 envelope, p50 and peak RSS): an `or-join` of two branches keyed on a value (`[?e :group 7] [?e :age ?a] (or-join [?a] (and [?f :group 17] [?f :age ?a] [(< ?a 30)]) (and [?g :group 27] [?g :age ?a] [(> ?a 60)]))`, both hashed) 111 ms → 8.3 ms at 100K facts, 1.44 s → 80 ms and 306 → 7 MiB at 1M, 17.1 s → 0.86 s and 1.9 GiB → 12 MiB at 10M. Other workloads unchanged. Results are unchanged (`test-oracle`). - **A join with no shared variable builds on the side with the smaller product estimate** (#473, part 7: #549; #575). A `HashJoin` with no join key holds one side in full, and the planner compared the inner pattern with the outer side's cheapest pattern, so a chain of patterns sharing no variable built every later join on the growing outer side (3^(k−1) rows at the k-th join of the #575 fuzz shape). It now compares the inner pattern with the product of the outer patterns' estimates, so such a chain builds on each 3-row inner pattern. Answers do not change; joins with a key are planned as before. - **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. @@ -108,6 +110,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Tests +- **Statement bases and large write transactions (#550).** A `WriteTransaction` whose statements repeat, change, retract and re-assert each other's facts across chunks gives every statement the same outcome, and stores the same records, at chunk sizes 1 to 4 as with one chunk; queries after each statement return what a commit of the statements so far would hold; failed and rolled-back statements and transactions leave the file passing `verify`. The fault matrix covers a large `WriteTransaction` at every write and sync, and with `test-oracle` the crash-kill test runs every third transaction of its large variant as one. - **Golden-file compatibility corpus (#391).** `tests/golden/` holds v7 files written by minigraf 2.0.3, each with a JSON manifest of its CRC32, `tx_count` and expected query results. They cover one checkpoint, several checkpoints, indexes rebuilt on open, a WAL left by a crash, a WAL whose entries were already checkpointed, and same-transaction multi-values (#371). `tests/golden_corpus_test.rs` opens a copy of each file and checks its manifest after open, after a checkpoint and reopen, and after one more write. Golden files are never regenerated, only added; a new `golden-corpus` job in `policy.yml` fails a pull request that changes one. The generator is a standalone crate pinned to `minigraf = "=2.0.3"` (`tests/golden/gen/v7/`). On `v3`, each v7 file must also carry a v8 meta page after its first open, and seven v8 files are frozen alongside them, written by the `v3` branch at `23aa57c` (`tests/golden/gen/v8/`): one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values (a 4,068-byte string stored twice, the 64/65-byte inline boundary, a 1,000-byte attribute and keyword). All #371 queries now pass. - **Model-based storage test (#385).** `tests/model_based_test.rs` runs random sequences of `transact` (multi-valued batches, transaction- and fact-level valid-time windows, a triple repeated with another window), `retract`, write transactions (committed or rolled back, retracting their own assertions), checkpoints, reopens (default, a 4-page cache, auto-checkpoint every 2 writes) and simulated crashes (a copy of the `.graph` file and WAL taken while the handle is open, so the WAL is replayed) against a file in a temp dir. After every step, `current_tx_count`, `verify`, full rows with windows and tx counts, and entity-, entity+attribute-, attribute-, attribute+value-, value-bound and full-scan queries, under `:as-of N` and `:valid-at T`, must match a plain reference model (one valid-time window per triple, #435; API-011 for two windows of one triple in one statement and API-019 for an empty or inverted window, from `execute` and `tx.execute`, #436; the last statement that writes a triple decides it at commit, #477). Reads inside a write transaction are checked against what its commit will hold. Normal CI runs 24 cases; the nightly property-test workflow runs 30,000. - **SIGKILL crash test checks committed data (#384).** `tests/crash_kill_test.rs` used to check only that the file reopened and one attribute query ran, so it missed #370 and could not reach #371. The child now runs a seeded workload (multi-valued batches, batched retracts, re-assertions) and logs each transaction after `execute` returns; it checkpoints after every transaction, every third, never (WAL replay), automatically every 2 writes, or every third with `SyncMode::Normal`. After a `SIGKILL` at a random point, the reopened file must hold exactly the model after the last logged transaction or the one in flight, through a full scan, attribute (AEVT), attribute+value (AVET) and entity-bound (EAVT) queries and `:as-of`, with `verify` clean. The checks run again after a second reopen and after a checkpoint plus reopen. Per-PR CI runs 5 rounds (one per mode); the nightly crash-kill workflow runs 100 per OS. `MINIGRAF_CRASH_KILL_SEED` replays a failure. diff --git a/CLAUDE.md b/CLAUDE.md index b3e0c9786c..54ae923fa7 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -104,7 +104,7 @@ cargo run < demos/demo_negation.txt 1. **`src/graph/`** — EAV fact store with bi-temporal support - `types.rs`: `Fact`, `Value`, `EntityId`, `TxId`, `VALID_TIME_FOREVER` - - `storage.rs`: `FactStorage` — in-memory store, `snapshot()` → `Snapshot` (committed reader + pin + pending prefix; every query/cursor/log read goes through one), `transact_batch`, `retract`, `get_facts_as_of`, `get_facts_valid_at`, `net_asserted_facts`, `get_facts_by_entity_attribute_indexed` + - `storage.rs`: `FactStorage` — in-memory store, `snapshot()` → `Snapshot` (committed reader + pin + pending prefix, and a `WriteTransaction`'s staged facts read with the pending ones as one store, #550; every query/cursor/log read goes through one), `transact_batch`, `retract`, `get_facts_as_of`, `get_facts_valid_at`, `net_asserted_facts`, `get_facts_by_entity_attribute_indexed` 2. **`src/storage/`** — Persistence layer - `mod.rs`: `StorageBackend` trait, `LegacyHeaderV7` (v7 migration only), `CommittedReader` trait @@ -126,7 +126,7 @@ cargo run < demos/demo_negation.txt - `dir_sync.rs`: `sync_parent_dir` — fsyncs the parent directory after creating the `.graph`/WAL or deleting the WAL (no-op off Unix) - `packed_pages.rs`: v7 fact pages, read only for migration - `persistent_facts.rs`: `PersistentFactStorage` — v8 save/load, auto-migration v7→v8 - - `persistent_facts/large_tx.rs`: large transactions (#550): `Minigraf::execute` of a statement over `TX_CHUNK_FACTS` facts on a file database becomes large (WAL guard: the WAL exists, header only, before any page; cache generation bound `g + 1`; next `tx_count` reserved, allocated at the commit point; `tx_id` fixed), writes each chunk into copy-on-write working trees (per-chunk `Encoder` over the working DICT, no `SharedDictCache`; a fact an earlier chunk wrote kept once, another window of its triple `API-011`; replaced pages it wrote released to the allocator, `g`'s freed), and commits as a checkpoint (pending store included, meta `g + 1`, WAL deleted). A statement error rolls back (cache bound `g`, written pages evicted, handle dirty so the next checkpoint writes a meta before deleting the WAL); an I/O failure also marks the handle failed (`STG-046`). A WAL found at open also marks the handle dirty. `WriteTransaction` stays on the staged path until #550 PR 3 + - `persistent_facts/large_tx.rs`: large transactions (#550): a transaction whose staged facts would pass `OpenOptions::transaction_chunk_facts` (default 65,536, clamped to 1..=1,000,000, the WAL entry limit) on a file database (`Minigraf::execute` of a larger statement, or a `WriteTransaction` statement that takes it over) becomes large (WAL guard: the WAL exists, header only, before any page; cache generation bound `g + 1`; next `tx_count` reserved, allocated at the commit point; `tx_id` fixed; the pending store written as the first chunk, so in-transaction reads see the working trees alone), writes each chunk into copy-on-write working trees (per-chunk `Encoder` over the working DICT, no `SharedDictCache`; a fact the statement wrote kept once, another window of its triple `API-011`; an earlier statement's keys of a triple it writes deleted, and the triple recorded in the statement's claims tree; replaced pages: written since the statement's base released, written before it held, `g`'s freed), and commits as a checkpoint (meta `g + 1`, WAL deleted). In a `WriteTransaction` each statement has a base (roots, counters, `freed` length, `PageAllocator::begin_base` ids): a rejected statement returns to it and the transaction stays usable; staged statements are written as one chunk when it becomes large (their windows checked at its `tx_id` first). `Minigraf::execute`'s statement error rolls back (cache bound `g`, written pages evicted, handle dirty so the next checkpoint writes a meta before deleting the WAL); an I/O failure also marks the handle failed (`STG-046`). A WAL found at open also marks the handle dirty 3. **`src/query/datalog/`** — Datalog engine - `parser.rs`: EDN/Datalog parser — `transact`, `retract`, `query`, `rule`, `:as-of`, `:valid-at`, `not`, `not-join`; `resolve_pseudo_sources` names each per-fact pseudo-attribute's source (nearest earlier same-entity pattern, lexical scope) and its hidden metadata variable `?#.`, else PRS-081 (#594) @@ -149,7 +149,7 @@ cargo run < demos/demo_negation.txt 5. **`src/repl.rs`** — Interactive REPL; TTY-aware (suppresses prompts/banner for piped input) -6. **`src/db.rs`** — Public API: `Minigraf::open/execute/query/fact_log/prepare/begin_write/checkpoint/save/verify/rebuild_indexes`, `WriteTransaction`, `IntegrityReport`, `OpenOptions::page_cache_size`, `OpenOptions::read_only` (#429: shared lock, nothing written, writes are `API-014`), `OpenOptions::query_memory_limit` (#549: `QRY-012`, off by default) +6. **`src/db.rs`** — Public API: `Minigraf::open/execute/query/fact_log/prepare/begin_write/checkpoint/save/verify/rebuild_indexes`, `WriteTransaction`, `IntegrityReport`, `OpenOptions::page_cache_size`, `OpenOptions::read_only` (#429: shared lock, nothing written, writes are `API-014`), `OpenOptions::query_memory_limit` (#549: `QRY-012`, off by default), `OpenOptions::transaction_chunk_facts` (#550) - `src/cursor.rs`: `Cursor` / `Batch` — owned, `Send` cursor returned by `Minigraf::query` and `PreparedQuery::query` (#432); pulls engine queries one internal batch at a time (`close`/drop stops the work; a read error after some rows comes on the next call), other queries computed at open; holds a `Snapshot` (one state of the store, its committed generation pinned, #543) until dropped - `src/fact_log.rs`: `FactLog` / `FactFilter` / `FactRecord` / `FactOrder` — every fact version streamed by `Minigraf::fact_log` (#430): tx order (multi-pass, bounded window) or storage order, key-level filters; an open log pins the committed generation (`storage::pins`), so checkpoints run but do not reuse its pages (`API-013` deprecated, #543) - `src/log_writer.rs`: `LogWriter` — builds a new file from `FactRecord`s with their tx and valid-time kept (#431): tx-ordered appends with holes (`API-015`/`API-016`), batched copy-on-write checkpoints at tx boundaries, no WAL, built at `.partial` and renamed by `finish` (`STG-043` if the target exists) @@ -208,7 +208,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1752 tests** (1738 passing, 14 ignored; unit + integration + doc). +**1767 tests** (1753 passing, 14 ignored; unit + integration + doc). 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/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 5e7b434754..fd9b033c0d 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-22 with `cargo test --quiet` -**Result**: 1,738 passing tests and 14 ignored tests (1,752 total) +**Result**: 1,753 passing tests and 14 ignored tests (1,767 total) This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Coverage-gate tests (#396) check that replay stops at a WAL entry whose first fact is longer than 10 MB or that claims more than 1M facts, that a WAL writer cannot be opened in a missing directory, and that a failed cut of a torn WAL tail fails the open and leaves the file as it was; that a short v7 page and a slot past the record count are `INT-024`; that a migration backup meta of another generation or file length is not used (`STG-032`, file unchanged), and a torn first meta with data in page 1 is `STG-032`, not a new file; that `save` with nothing pending writes nothing, `into_backend` saves pending facts, and `rebuild_indexes` with nothing checkpointed commits the pending facts; and that unsorted or repeated B+tree input and a stored key inserted with another value are `INT-049`, a tree pointer to a free-list page is `STG-013` from `get`, a leaf walk and a copy-on-write insert, and the read-only `MutexStorageBackend` refuses writes, syncs and close. A page-cache test holds two threads in the backend read so both miss the same page, and checks that both get the one cached copy; before it, that path ran only when the scheduler happened to race the threads, and the gate flapped. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 956 passing; ten that spawn threads or a child process are ignored on WASI. These are not counted above. A WAL test checks that a checkpoint with no facts to flush still removes a WAL whose entries are all already in the file, and the golden-corpus test now requires the WAL to be gone after a checkpoint for the `stale_wal` fixtures too (#457). A WAL test checks that closing a handle opened with `wal_checkpoint_threshold(usize::MAX)`, in both sync modes, leaves the `.graph` file byte for byte as it was and keeps the WAL, whose entries replay on the next open, and a unit test closes an in-memory handle under the same setting (#476). A recursive-rule test checks that a rule query on a database with more live facts than `max_results` returns its answer, with a bound and with a free first argument, and that a query deriving more facts than its `:max-results` is still `INT-020` (#528). A log-writer test runs the online backup from `docs/DURABILITY.md`: it copies a read-write handle with an uncheckpointed transaction through `fact_log` and `LogWriter` while another thread writes past the automatic checkpoint threshold, and checks that the copy verifies clean, holds exactly the records the log returned and the counter read after the log opened, and that every concurrent write reaches the source's file once the log is dropped (#398). Rule-body tests in `tests/recursive_rules_test.rs` check that a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths (#617). Tests in `tests/not_join_test.rs` check that a rule calling a rule with `not-join`, `not` or `or` returns that rule's rows, with a free and a literal argument and through a forwarding rule, and that a rule with its own `not-join` calling one gets the same rows whether or not the query asks for the callee first; stratification unit tests check that such a caller, a rule forwarding to it and a caller of a recursive one sit above the callee, and that recursion through a rule with a `not` still stratifies (#628). Tests in `tests/not_join_test.rs` check that recursion through a rule with `not`, `not-join` or `or`, directly or through another rule, returns every row along a chain, and that the `not` still removes the rows it should; evaluator unit tests check that such recursion stops at its fixpoint that `max_iterations` and `max_results` end one that does not with INT-020, and that `max_results` counts the facts every pass derives, not only the mixed rule's (#633). @@ -31,7 +31,8 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Parser vs grammar** (`src/query/datalog/parser/verifier.rs`, 4 tests; #643): about 1.07M lexical strings and 555K structural inputs at the default bound (7.6M at `MINIGRAF_GRAMMAR_BOUND=4`) checked against `tests/grammar/grammar.pest`; known drift by cause in `KNOWN_DRIFT` (none left: #650, #651 fixed), semantic codes with witnesses in `SEMANTIC`. - **Statement reader** (`src/query/datalog/parser/statement.rs`, 8 tests; `tests/read_only_open_test.rs`, 1 test; #550): every `transact`/`retract` built from up to three of 34 statement tokens (balanced or not) in 10 templates, and a corpus of statements with errors in several phases (a later lexer error over an earlier structure error, a later structure error over an earlier fact error, phase 3 in today's check order, too-deep nesting inside a fact and an extra element), give the same command or error through the reader as through the whole-input parser, and the same facts or error through the write path at chunk sizes 1, 2, 3 and the default; the sequences raise 24 distinct codes and reach pass 2; pass 2 resumes just after the last kept fact; materialisation and window errors come with the facts, after `API-014` on a read-only database; the parser's `keep` flag checks structure and holds nothing; lexer offsets are byte offsets. - **Copy-on-write delete** (`src/storage/btree.rs`, 3 tests; #550): `cow_update` against a `BTreeSet` model over random insert and delete batches (samples, contiguous runs that empty leaves and subtrees, a deleted key inserted again) on trees of 0 to 60,000 keys, each step walked as `verify` walks a tree, every page of the old tree unchanged, `freed` exactly the old nodes dropped; deleting everything, front half first, gives root 0 and root 0 takes inserts again; a missing, unsorted or repeated delete, or a delete on root 0, is `INT-049`. -- **Large transactions** (`src/storage/persistent_facts/large_tx.rs`, 7 tests; `src/fault_matrix.rs`, 4 tests; `src/storage/page.rs`, 2 tests; `src/storage/cache.rs`, `src/storage/btree.rs` and `statement.rs`, 4 tests; #550): a `transact`/`retract` of more than one chunk, run by `Minigraf::execute` on a file database at chunk sizes 1 to 4, stores the same records as the one-chunk path (repeats across chunks stored once, several values and windows of one attribute, shared long values, refs, keywords, transaction-level windows, retractions, pending WAL entries committed with it), returns its `tx_id`, answers `:as-of`, passes `verify`, deletes the WAL and survives reopen; another window of a triple an earlier chunk wrote (`API-011`) and a value too long for a checkpoint in a later chunk (`WAL-003`) give the one-chunk path's code and message, take no `tx_count`, write no meta and leave the WAL, and the next checkpoint writes a meta before deleting it, as the first checkpoint after an open with a WAL does; a crash before the meta write on a new file reopens through the WAL guard, and is `STG-033` without it; cursors and fact logs opened before and between chunks keep their snapshot through later checkpoints. The fault matrix injects every write and sync fault at every call of a large transaction on a file with one and with two valid meta slots, with and without a WAL beforehand. Allocator tracking and release, cache eviction, and cursor peeking have unit tests. With `test-oracle`, `tests/crash_kill_test.rs` adds a variant whose child makes most transactions large and rolls back a large statement after writing pages, and `tests/model_based_test.rs` runs at a chunk size of 2; `tests/large_transaction_acceptance_test.rs` (ignored, `test-oracle` only, nightly in `.github/workflows/smoke.yml`) holds at most 16,384 materialised facts for a 1M-fact `transact` and prints peak RSS. +- **Large transactions** (`src/storage/persistent_facts/large_tx.rs`, 7 tests; `src/fault_matrix.rs`, 4 tests; `src/storage/page.rs`, 2 tests; `src/storage/cache.rs`, `src/storage/btree.rs` and `statement.rs`, 4 tests; #550): a `transact`/`retract` of more than one chunk, run by `Minigraf::execute` on a file database at chunk sizes 1 to 4, stores the same records as the one-chunk path (repeats across chunks stored once, several values and windows of one attribute, shared long values, refs, keywords, transaction-level windows, retractions, pending WAL entries committed with it), returns its `tx_id`, answers `:as-of`, passes `verify`, deletes the WAL and survives reopen; another window of a triple an earlier chunk wrote (`API-011`) and a value too long for a checkpoint in a later chunk (`WAL-003`) give the one-chunk path's code and message, take no `tx_count`, write no meta and leave the WAL, and the next checkpoint writes a meta before deleting it, as the first checkpoint after an open with a WAL does; a crash before the meta write on a new file reopens through the WAL guard, and is `STG-033` without it; cursors and fact logs opened before and between chunks keep their snapshot through later checkpoints. The fault matrix injects every write and sync fault at every call of a large transaction on a file with one and with two valid meta slots, with and without a WAL beforehand. Allocator tracking and release, cache eviction, and cursor peeking have unit tests. With `test-oracle`, `tests/crash_kill_test.rs` adds a variant whose child makes most transactions large and rolls back a large statement after writing pages, and `tests/model_based_test.rs` runs at a chunk size of 2; `tests/large_transaction_acceptance_test.rs` (ignored, `test-oracle` only, nightly in `.github/workflows/smoke.yml`) holds at most 65,536 materialised facts (the default chunk) for a 1M-fact `transact` and prints peak RSS. +- **Statement bases and large write transactions** (`src/storage/persistent_facts/large_tx.rs`, 9 tests; `src/fault_matrix.rs`, 4 tests; `src/storage/page.rs` and `src/storage/btree.rs`, 2 tests; `tests/memory_limit_test.rs`, 1 test changed; #550): a `WriteTransaction` of statements that repeat, change, retract and re-assert earlier statements' facts within and across chunks, including two that fail `API-011` (one only through a repeat of an earlier statement's fact, the claims case), run at chunk sizes 1 to 4, gives every statement the small path's outcome and stores the same records, over one transaction and over two with committed and pending facts between them, passes `verify` and survives reopen; queries after each statement, inside the transaction at chunk sizes none and 1 to 4, return what a commit of the statements so far holds (including a staged retraction of a pending assertion and the reverse); a failed statement that replaced pages of the committed generation leaves them in use (`verify` after later checkpoints); a rolled-back large transaction leaves the file, generation and records as they were and the next checkpoint writes a meta; one whose only statement failed commits nothing and takes no `tx_count`; a staged window that has ended when the transaction becomes large rejects that statement with `API-019`, writes nothing and leaves the transaction small; a failed handle is refused (`STG-046`) when a transaction would become large, and a write failure inside one fails its commit with `STG-046` and leaves the file as it was. The fault matrix injects every fault at every call of a large `WriteTransaction` (staged statement, large statement, a failing one, then one changing earlier triples) on one and two meta slots, with and without a WAL. `OpenOptions::transaction_chunk_facts` sets the chunk size (0 is 1, above 1,000,000 is 1,000,000). Base id tracking and `tree_pages` have unit tests. With `test-oracle`, the crash-kill `Large` variant runs every third transaction as a `WriteTransaction` of three statements, and the model-based test's write-transaction steps cross chunks and statement bases at chunk size 2. Queries inside a write transaction run on the engine and count toward `query_memory_limit` with staged writes too. - **Grammar page** (`tests/grammar_doc.rs`, 10 tests; #643): `docs/GRAMMAR.md` matches the EBNF rendered from `tests/grammar/grammar.pest`; each rendering rule (sequence, choice and grouping, names and builtins, `SOI`/`EOI` dropped, lookaheads as comments, bounded repetition, quoting, token marks, section titles, line breaking, the whitespace note and the comment note it joins) on a small grammar. - **Plan independence** (`tests/plan_independence_test.rs`, 15 tests, `test-oracle` feature only; #596): a matrix of queries (joins in both text orders, cross products, keyword and ref, floats, long strings, filter and binding expressions, recursive rules and rules with `not`, `or`/`or-join` including the #250 short-circuit shapes, placed and deferred `not`/`not-join`, aggregates, `:as-of`, `:valid-at`, `:any-valid-time`), in memory and on file after a checkpoint and a reopen, through `execute` and a cursor, gives the same bag of rows with clause reordering on and off (`minigraf::__reorder`) and with the engine's negation bodies and `or` branches chosen, forced hashed and forced correlated (`minigraf::__subplans`, #546; the matrix gains #546's negation and disjunction shapes); #596's example and the unification cases (an expression whose output is its input, two expressions on one variable, integer vs float, `-0.0` vs `0.0`); and `or` / `or-join` branches whose expressions read or bind from a variable only the outer row binds, nested and in rule bodies (#620); and expressions, chains of them and a `not` after them, reading a variable only an `or` binds, in queries, with rules and in rule bodies (#625; `tests/disjunction_test.rs` repeats them without `test-oracle`). Under `test-oracle` the model-based and property tests also rerun every generated query with reordering off (the property test also with negation bodies and `or` branches forced hashed; it generates `or` / `or-join` over bound variables, #546). Unit tests cover `branch_outer_reads` (#620), the planner deferring an expression only an `or` can bind for, after the expressions placed before it and ahead of the deferred `not`s (#625), `apply_expr` (equal, different, integer vs float, NaN, `-0.0`/`0.0` with and without replacing, keyword vs ref both ways, a failing expression), `Binders::expression`, the switch (source order kept, per thread, restored on drop), and the engine planner's `Bind` modes and build side with the switch off; the engine's join matrix gains six unification shapes. - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). diff --git a/docs/superpowers/plans/2026-10-21-550-streaming-transactions.md b/docs/superpowers/plans/2026-10-21-550-streaming-transactions.md index bc9c8c968d..2c2982e845 100644 --- a/docs/superpowers/plans/2026-10-21-550-streaming-transactions.md +++ b/docs/superpowers/plans/2026-10-21-550-streaming-transactions.md @@ -273,8 +273,207 @@ statement takes today's path: `CLAUDE.md`'s module notes for `large_tx.rs`. No `CHANGELOG.md` or docs-site change (PR 3). -## PR 3 +## PR 3: statement bases, large `WriteTransaction`s, reads -Planned in detail when PR 2 is merged, against the code it leaves: spec §5 and §7, the large -path for every `WriteTransaction` statement (decision 12), the measurement on the bench -machine, the final `TX_CHUNK_FACTS`, and the docs listed in spec §9. +Checked against `v3` at `75a3faca` (PR 2 merged as `9ecc02f5`). Line numbers are from that +commit. + +### Scope + +- A `WriteTransaction` on a writable file database becomes large (spec §2, §4.1) and keeps its + `LargeTx` across `execute` calls; `commit`, `rollback` and drop go through `commit_large` and + `rollback_large`. In-memory databases stay small, as for `execute` (PR 2 scope). +- Statement bases (spec §5) for every statement of a large transaction after its first write. +- Every `WriteTransaction` query reads a `Snapshot` (spec §7); `merged_query_facts` + (`db.rs:1770`) and the executor's `facts_override` (`executor.rs:150`) go. +- The measurement (spec §8.2), the final `TX_CHUNK_FACTS`, and the docs of spec §9. + +Not in PR 3: #686 (WAL entries over 1M facts, its own v3 PR and v2.x backport), #687 +(`crash-kill.yml` on `main`), #551. + +### Decisions not fixed by the spec (PR 3) + +25. **When a `WriteTransaction` becomes large.** `WriteTransaction` gains `large: + Option` (not wasm32). A statement read by pass 1 makes a small transaction on a + `WriteContext::File` large when it is large itself (`Statement::is_large`) or when its + facts plus the staged ones number more than `tx_chunk_facts()` (spec §2). A small + statement's phase 5–7 errors (`Statement::facts`, `check_one_window_per_triple`) are + reported before the switch, so a statement rejected as today leaves the transaction small, + as today. A large statement's errors come from its chunks, after the switch. +26. **Order of the switch** (spec §4.1). `tx_id = tx_id_now()`; then step 5's checks, before + steps 1–4: the staged facts reduced by `keep_last_statement` are checked by + `check_valid_windows` at `tx_id` and `wal::check_fact_size` (the checks `check_chunk`, + `large_tx.rs:290`, runs; each statement passed `API-011` and the reduction leaves one + statement per triple). A failure rejects the current statement with nothing to undo: no WAL + guard, no bound, the staged facts as they were. Then `refuse_if_failed` (`STG-046` / + `WAL-007`: a large transaction writes pages, so a failed handle is refused here, not at + commit), the WAL guard, `begin_large(tx_id)`, and the staged facts as one chunk, taken from + the transaction only now. An error writing them is a failure: they passed every statement + check, and the fast path (§5.2) finds no key of this `tx_count`. +27. **The pending store is written when the transaction becomes large, not at commit** (spec + §4.3 step 1). `begin_large` writes `get_pending_facts()` (own `tx_count`s, no checks) as + its first chunk and records their number in `LargeTx::pending_len`; `commit_large` publishes + with it. A query inside a large transaction (§7) then reads the working trees alone: the + engine's scan treats the committed reader as older than the pending part (a committed + triple with a pending record is shadowed, `scan.rs:448-456`) and so does the executor's + net-assert over committed survivors plus pending records (`storage.rs:232`); with pending + facts older than the working trees' newest, both would let a pending assertion hide this + transaction's retraction. No fact joins the pending store while the write lock is held + (`execute_statement`, `commit_inner` and WAL replay at open append under it), so the length + at `begin_large` is the publish count. One path for `Minigraf::execute` and + `WriteTransaction`; an error writing the pending chunk fails the handle and rolls back. +28. **The base** (spec §5.1). `Base { roots: [u64; 5], next_eid, next_iid, fact_count, + freed_len, held: Vec, claims: u64 }` in `LargeTx`, recorded when a statement of a + large `WriteTransaction` starts (decision 33). `PageAllocator::begin_base` starts a second + id set beside `handed`, `since`: `alloc` and `alloc_append` add to it, `release` removes + from it; `handed_since(id)`; `end_base()` takes it. +29. **Replaced pages with a base** (spec §4.2 step 3): `handed_since` → released (and out of + `since`); not `handed` (generation `g` references it) → `freed`; otherwise → `held`. +30. **Which statement wrote a key: claims** (deviation from spec §5.2). Spec §5.2 step 2 says a + key of this `tx_count` that is in the base's EAVT tree came from an earlier statement. Not + when this statement wrote the same key in an earlier chunk: statement 1 asserts `[:a :n 1]`, + statement 2 asserts `[:a :n 1]` in chunk 1 (§5.2 deletes statement 1's key and inserts the + same bytes) and `[:a :n 1 {other window}]` in chunk 2. The key is in the base, so chunk 2 + would delete it and accept the statement; a small transaction rejects it with `API-011`. + The base holds the keys, not who wrote them last. So a statement also keeps **claims**: a + copy-on-write B+tree (root 0 at the base, pages from the allocator, so in `since`) of the + triples (EAVT key prefix up to `keys::triple_len`) whose base keys it deleted. For each + triple `T` of a chunk, with `R` its working EAVT keys of this `tx_count` (`repeats`' run): + - `R` empty, the fast path, or `T` in claims: `R` is this statement's (repeat or `API-011`, + as in PR 2); + - otherwise, if `R`'s first key is in the base's EAVT tree (`btree::get`): `R` is earlier + statements' (this statement never touched `T`, or it would be in claims; and before it + touches `T` every key of `T` is the base's) — every key of `R` and its AEVT, AVET and + VAET keys go into the chunk's deletes, the records are inserted, and `T` joins claims; + - otherwise `R` is this statement's: the base has no key of `T`, so it never will. + Claims hold only triples two statements of the transaction share, on pages, not in memory. + Their replaced pages are released at once. At the end of the statement every claims page + is released (`btree::tree_pages`, new: the ids of a tree's nodes). +31. **A failed statement restores `freed`** (spec §5.3 gap). Pages of `g` that the statement + replaced went to `freed`; the restored roots reference them again, so `freed` is truncated + to its length at the base. Success releases `held` and the claims pages; failure restores + the roots, counters and `fact_count`, truncates `freed`, releases `since` (claims pages + included), keeps `held`. +32. **Statement errors and failures in a large `WriteTransaction`.** Statement errors + (`API-011`, `API-019` at the fixed `tx_id`, `WAL-003`, pass 2 errors) restore the base; the + transaction stays large and usable. Failures (decision 18) fail the handle; the transaction + stays open, `commit` returns `STG-046` and rolls back, as `rollback` and drop do. +33. **Every statement of a large `WriteTransaction` gets a base**, the first written one + included. A statement error in a first large statement must leave the transaction usable, + which PR 2's rollback does not (`execute_large` ends the transaction). In the fast path + (§5.2: no earlier statement in the working trees) the claims stay empty, since it never + deletes. `Minigraf::execute`'s one statement keeps PR 2's rollback and no base (decision + 13). The staged chunk of decision 26 is written without a base: it cannot fail but as a + failure. +34. **Phase 6 of a large transaction's later statements** runs in pass 1 at the fixed `tx_id`, + which every fact is stamped with; a small transaction keeps the staging time. +35. **Reads** (spec §7). `Snapshot` gains `staged: Option>`, built from the + staged facts with each default `valid_from` resolved to its staged `tx_id` + (`merged_query_facts`' rule), and `now` raised to the newest staged `tx_id` + (`pending_read_now_floor`'s rule). Every pending read (`all_facts`, `live_facts_of_scans`, + `pending_records`, `pending_live`, `pending_range`, `pending_len`) reads the pending store's + first `pending_len` facts and then `staged` as one store: positions `pending_len..` are + staged, and index walks merge the two `BTreeMap`s in key order, so `pending_live` decides a + triple over both. Keys never collide: staged `tx_count`s are above every pending one. A + large transaction's snapshot has `committed` = an `OnDiskReader` over the working meta + (`last_checkpointed_tx_count` = its `tx_count`), unpinned working pages (the pin `snapshot()` + takes on `g` stays; it costs nothing under the write lock), `pending_len` 0 (decision 27) + and no `staged`. `DatalogExecutor::new_from_facts_with_rules_and_functions`, + `facts_override` and `read_now_floor` are removed; `WriteTransaction` queries run on the + engine where it plans them, with the oracle under `test`. +36. **Measurement** is a program outside the repository (public API only, so it builds on `v3` + before #550, `d24fb585`, and on this branch), one process per run for `VmHWM`; pages + written from `/proc/self/io` `write_bytes` / 4096 (WAL included). The chunk size is set by + building with each value of the constant. Results (no machine details) go in the PR and in + this plan. + +### Measurement results (step 22) + +`v3` before #550 (`d24fb585`) against this branch at each chunk size, 1M facts, an idle 88-vCPU +machine, one process per run, `opt-level = 3`. Facts are `[:e :a v]`: sequential +entities `k = i / 10`, random entities `k` uniform over 100K; short values are integers, long +ones unique 100-byte strings. RSS is `VmHWM` above the peak while the input text was built +(the input itself is 31–475 MiB); 0 means no rise above it. Pages written are +`write_bytes / 4096`, WAL included; file pages after the commit and a checkpoint. + +| Shape | v3 before | 4,096 | 16,384 | 65,536 | +|---|---|---|---|---| +| `execute`, sequential, short | 9.1 s, 1,312 MiB, 21,075 | 4.9 s, 0, 23,423 | 4.2 s, 0, 22,006 | 3.9 s, 0, 21,933 | +| `execute`, sequential, long | 15.2 s, 2,102 MiB, 90,715 | 21.8 s, 0, 95,855 | 20.2 s, 0, 95,284 | 21.0 s, 0, 98,430 | +| `execute`, random, short | 11.4 s, 1,293 MiB, 20,394 | 36.4 s, 0, 24,751 | 18.5 s, 0, 26,605 | 9.5 s, 0, 28,110 | +| `execute`, random, long | 17.6 s, 2,087 MiB, 82,678 | 51.0 s, 0, 90,095 | 39.7 s, 0, 97,778 | 28.1 s, 0, 104,613 | +| 10 statements, sequential, short | 10.1 s, 1,391 MiB, 21,075 | 5.0 s, 0, 24,195 | 4.5 s, 4, 22,920 | 3.8 s, 41, 22,832 | +| 10 statements, sequential, long | 17.5 s, 2,419 MiB, 90,715 | 22.1 s, 0, 109,067 | 20.6 s, 0, 107,432 | 18.9 s, 47, 107,477 | +| 10 statements, random, short | 12.0 s, 1,372 MiB, 20,394 | 38.2 s, 0, 36,912 | 22.5 s, 7, 38,596 | 10.1 s, 41, 41,418 | +| 10 statements, random, long | 22.3 s, 2,402 MiB, 82,678 | 51.3 s, 0, 139,352 | 41.3 s, 0, 146,629 | 34.0 s, 54, 150,977 | + +At 100K facts every chunk size is within 2.3× of `v3` before in time and under 110 MiB of RSS +(before: 142–260 MiB). **The chunk size becomes `OpenOptions::transaction_chunk_facts`, +default 65,536** (user decision, 2026-10-22: configurable, default optimised for speed; this +deviates from spec decision 2's memory first): 65,536 takes about half the time of 16,384 with +random entities for 40–55 MiB more, and 4,096 is up to 3× slower than 16,384. Values are kept +between 1 and 1,000,000, the most facts WAL replay reads from one entry (`wal.rs` +`MAX_FACTS_PER_ENTRY`), since a small transaction is one entry (#686). Two costs the measurement shows: random entities are slower +than before (each chunk rewrites leaves all over each tree, spec §8.2), and a transaction of +several statements over random entities leaves a file up to 1.8× larger, since every page its +base references and a statement replaces stays held until the statement ends (§4.2 step 3); +the space is free in the file afterwards. #551's envelope records the result. + +### Deviations from the spec (PR 3) + +1. Step 5's checks run before steps 1–4, so a rejected statement has nothing to undo (decision + 26; spec §4.1 step 5). +2. The pending store is written when the transaction becomes large (decision 27; spec §4.3 + step 1). +3. Claims decide which statement wrote a key, not membership in the base alone (decision 30; + spec §5.2 step 2). +4. A failed statement truncates `freed` (decision 31; spec §5.3 does not cover it). +5. A small statement's `API-011` is checked before the switch (decision 25). +6. Every statement of a large `WriteTransaction` has a base, the fast path included (decision 33). +7. A large transaction in which no statement wrote a fact commits nothing and takes no + `tx_count`, as a small one with nothing staged: `commit` rolls it back (found by the + model-based test). +8. Inside a large transaction, `:as-of` its own `tx_count` sees every finished statement; in a + small one each staged statement has its own synthetic count until `commit`. +9. The chunk size is an open option, `OpenOptions::transaction_chunk_facts`, default 65,536, + not a constant (spec §8.1, decision 2; user decision after the measurement). + +### PR 3 steps + +16. **Allocator and B+tree.** `PageAllocator::begin_base`, `handed_since`, `end_base` + (decision 28); `btree::tree_pages`. Unit tests: `since` covers ids handed after + `begin_base` and not before, `release` removes from it, `tree_pages` lists exactly the + pages a `cow_update`d tree reaches. +17. **Pending chunk at the switch** (decision 27): `begin_large` writes the pending store; + `commit_large` publishes `tx.pending_len`. PR 2's tests pass unchanged. +18. **Bases and claims** (decisions 28–31, 33) in `large_tx.rs`: `begin_statement`, + `end_statement(ok)`, `repeats` generalised to `resolve` (drops, deletes for the four + index trees, claims), `apply_chunk` with deletes and `fact_count` decremented. Unit tests on + the file backend with chunk sizes 1–4: statement sequences in one large transaction + against the same statements in a small one (records equal, `API-011` in the same + statements), a failed statement leaves the trees, counters and `freed` at its base and the + transaction usable, a rolled-back transaction leaves `verify` clean and every page + accounted for after the next checkpoint. +19. **`WriteTransaction` large path** (decisions 25, 26, 32, 34): `execute_inner`, + `commit_inner`, `rollback`, `Drop`. Tests: a `WriteTransaction` differential at chunk sizes + 1–4 (`large_statements_store_what_small_ones_do` with the workload's statements in one + transaction, and split over several), the step 5 `API-019` case (a staged window that ends + between staging and the switch), a failed handle refused at the switch, commit after a + failure is `STG-046`. +20. **Reads** (decision 35): `Snapshot::staged`, the merged pending walk, the large + transaction's working-tree snapshot, the executor's override removed. Tests: + read-your-own-writes, `:as-of` of staged counts, retract-then-assert (#477) and + assert-then-retract across statements, small and large, each against the committed result; + a staged retraction hides a pending assertion of the same triple and vice versa; the + existing `db.rs` transaction read tests pass on the engine. +21. **Crash and faults.** Fault matrix: `Op::Large { tx: true, .. }` (a `WriteTransaction` of + a staged statement, the large `X`, a statement that fails `API-011` after writing a chunk, + and one that repeats and changes earlier statements' triples; chunk size 3), on one and two + meta slots, with and without a WAL. Crash-kill `Large` variant: every third transaction is a + `WriteTransaction` of the opposite statement, the failing large statement and the + transaction itself. The model-based test covers bases through its `WriteTransaction` steps + at chunk size 2. +22. **Measurement and `TX_CHUNK_FACTS`** (decision 36): set the constant here and in + `tests/large_transaction_acceptance_test.rs`. +23. **Docs.** `CHANGELOG.md`, `docs/TEST_COVERAGE.md`, `CLAUDE.md` (module notes, counts), and a + docs-site PR (`content/architecture.md`, ``). diff --git a/src/db.rs b/src/db.rs index 6a2d274a44..8aac4bcea5 100644 --- a/src/db.rs +++ b/src/db.rs @@ -199,10 +199,22 @@ pub struct OpenOptions { /// neither is the answer [`Minigraf::execute`] collects; read a large /// answer through [`Minigraf::query`]. `0` fails any query that keeps /// state. - /// - /// Queries inside a [`WriteTransaction`] that has staged writes are not - /// counted yet. pub query_memory_limit: usize, + /// The most facts a transaction holds in memory on a file database, and + /// so its chunk size (#550). Defaults to 65,536. + /// + /// A transaction whose facts would pass it is *large*: it writes them a + /// chunk at a time into the file's index trees and commits as a + /// checkpoint, with no WAL entry, so its memory stays at one chunk + /// whatever its size. At 1M facts the default held 40–55 MiB; 16,384 + /// held under 10 MiB but took up to twice as long when the facts were + /// spread over many entities. A large transaction's `tx_id` is the time + /// it became large. + /// + /// Kept between 1 and 1,000,000 (the most facts one WAL entry holds). In-memory + /// databases never write chunks; a statement is still read a chunk at a + /// time. + pub transaction_chunk_facts: usize, } #[allow(deprecated)] // `max_results`, kept as an alias until it is removed @@ -217,6 +229,7 @@ impl Default for OpenOptions { synchronous: SyncMode::Full, read_only: false, query_memory_limit: usize::MAX, + transaction_chunk_facts: statement::DEFAULT_TX_CHUNK_FACTS, } } } @@ -279,6 +292,14 @@ impl OpenOptions { self } + /// Set the most facts a transaction holds in memory. See + /// [`OpenOptions::transaction_chunk_facts`]. + #[must_use] + pub fn transaction_chunk_facts(mut self, facts: usize) -> Self { + self.transaction_chunk_facts = facts; + self + } + /// The limit rule queries run with: the lower of `max_derived_facts` and /// its deprecated alias `max_results` (#553). #[allow(deprecated)] @@ -773,7 +794,12 @@ impl Minigraf { fn execute_statement(&self, input: &str, kind: Kind) -> Result { // Before the lock, as parsing is: a malformed statement never waits. // Its materialisation and window errors come with its facts, below. - let statement = statement::read_statement(input, kind, crate::graph::types::tx_id_now())?; + let statement = statement::read_statement( + input, + kind, + crate::graph::types::tx_id_now(), + self.chunk_facts(), + )?; self.reject_if_read_only(kind.name())?; { let mut ctx = self @@ -905,6 +931,11 @@ impl Minigraf { wal.as_mut().ok_or_else(|| err_coded!(ErrorCode::Api009)) } + /// The statement chunk size (`OpenOptions::transaction_chunk_facts`). + fn chunk_facts(&self) -> usize { + statement::tx_chunk_facts(self.inner.options.transaction_chunk_facts) + } + /// The executor for a read-only command: no lock, the database's limits, /// every read from `snapshot`. fn read_executor(&self, snapshot: Snapshot) -> DatalogExecutor { @@ -1029,6 +1060,8 @@ impl Minigraf { next_pending_tx_count: self.inner.fact_storage.current_tx_count().saturating_add(1), next_pending_tx_id: crate::graph::types::tx_id_now(), committed: false, + #[cfg(not(target_arch = "wasm32"))] + large: None, }) } @@ -1541,6 +1574,19 @@ pub struct WriteTransaction<'a> { next_pending_tx_id: TxId, /// Set to `true` after a successful `commit()` to suppress rollback in `Drop`. committed: bool, + /// The working state once the transaction is large (#550 spec §4): its + /// statements are then in copy-on-write working trees, not staged. + #[cfg(not(target_arch = "wasm32"))] + large: Option, +} + +/// A statement that makes a `WriteTransaction` large (#550 plan decision 25). +#[cfg(not(target_arch = "wasm32"))] +enum Current<'s> { + /// At most one chunk of facts, checked through `API-011`. + Small(Vec), + /// A statement of more than one chunk. + Large(statement::Statement<'s>), } impl<'a> WriteTransaction<'a> { @@ -1561,13 +1607,37 @@ impl<'a> WriteTransaction<'a> { fn execute_inner(&mut self, input: &str) -> Result { if let Some(kind) = statement::kind_of(input) { + #[cfg(not(target_arch = "wasm32"))] + if let Some(tx) = &self.large { + // Every fact is stamped with the transaction's tx_id. + let chunk = statement::tx_chunk_facts(self.inner.options.transaction_chunk_facts); + let statement = statement::read_statement(input, kind, tx.tx_id(), chunk)?; + let chunks = statement.chunks()?; + refuse_if_failed(&self.guard)?; + self.write_statement(chunks)?; + return Ok(QueryResult::Ok); + } // A rejected statement stages nothing; the transaction stays // usable. Pass 1 checks windows at the staging time; `commit` // checks them again at the commit time. let staged_tx_id = std::cmp::max(crate::graph::types::tx_id_now(), self.next_pending_tx_id); - let facts = statement::read_statement(input, kind, staged_tx_id)?.facts()?; + let chunk = statement::tx_chunk_facts(self.inner.options.transaction_chunk_facts); + let statement = statement::read_statement(input, kind, staged_tx_id, chunk)?; + #[cfg(not(target_arch = "wasm32"))] + let file = matches!(*self.guard, WriteContext::File { .. }); + #[cfg(not(target_arch = "wasm32"))] + if file && statement.is_large() { + self.become_large(Current::Large(statement))?; + return Ok(QueryResult::Ok); + } + let facts = statement.facts()?; crate::graph::storage::check_one_window_per_triple(&facts)?; + #[cfg(not(target_arch = "wasm32"))] + if file && self.pending_facts.len().saturating_add(facts.len()) > chunk { + self.become_large(Current::Small(facts))?; + return Ok(QueryResult::Ok); + } self.stage_pending_facts(facts); return Ok(QueryResult::Ok); } @@ -1586,23 +1656,8 @@ impl<'a> WriteTransaction<'a> { } fn execute_read_command(&self, cmd: DatalogCommand) -> Result { - if self.pending_facts.is_empty() { - let mut executor = DatalogExecutor::new_with_rules_and_functions( - self.inner.fact_storage.clone(), - self.inner.rules.clone(), - self.inner.functions.clone(), - ); - executor.set_limits( - self.inner.options.derived_fact_limit(), - self.inner.options.query_memory_limit, - ); - return executor.execute(cmd); - } - - let merged_facts = self.merged_query_facts()?; - let mut executor = DatalogExecutor::new_from_facts_with_rules_and_functions( - merged_facts, - self.pending_read_now_floor(), + let mut executor = DatalogExecutor::new_with_rules_and_functions( + self.inner.fact_storage.clone(), self.inner.rules.clone(), self.inner.functions.clone(), ); @@ -1610,9 +1665,132 @@ impl<'a> WriteTransaction<'a> { self.inner.options.derived_fact_limit(), self.inner.options.query_memory_limit, ); + executor.set_snapshot(self.read_snapshot()?); executor.execute(cmd) } + /// The state a query inside the transaction reads (#550 spec §7): for a + /// large transaction its working trees, which hold every committed and + /// pending fact and its finished statements; otherwise the database with + /// the staged facts after its pending ones. + fn read_snapshot(&self) -> Result { + let snapshot = self.inner.fact_storage.snapshot()?; + #[cfg(not(target_arch = "wasm32"))] + if let (Some(tx), WriteContext::File { pfs, .. }) = (&self.large, &*self.guard) { + return Ok(snapshot.with_committed(pfs.large_reader(tx))); + } + // A default `valid_from` stays the sentinel until the commit stamps + // it; reads see it as the fact's own staged tx_id. + let staged = self + .pending_facts + .iter() + .cloned() + .map(|mut f| { + if f.asserted && f.valid_from == VALID_FROM_USE_TX_TIME { + f.valid_from = f.tx_id.cast_signed(); + } + f + }) + .collect(); + Ok(snapshot.with_staged(staged)) + } + + /// Make the transaction large with `current`, the statement that takes + /// it over `TX_CHUNK_FACTS` staged facts (#550 spec §4.1, plan decision + /// 26). The staged statements are checked at the transaction's `tx_id` + /// first: a failure rejects `current` and leaves the transaction small. + #[cfg(not(target_arch = "wasm32"))] + fn become_large(&mut self, current: Current<'_>) -> Result<()> { + let tx_id = crate::graph::types::tx_id_now(); + let keep = last_statement_mask(&self.pending_facts); + let kept = || { + self.pending_facts + .iter() + .zip(&keep) + .filter_map(|(f, k)| k.then_some(f)) + }; + for f in kept() { + crate::graph::storage::check_valid_windows(std::slice::from_ref(f), tx_id)?; + } + for f in kept() { + crate::wal::check_fact_size(f)?; + } + refuse_if_failed(&self.guard)?; + let WriteContext::File { + pfs, wal, db_path, .. + } = &mut *self.guard + else { + bail_coded!(ErrorCode::Int019, "a large transaction without a file"); + }; + // The WAL guard (§4.5), before any page is written. + Minigraf::open_wal( + wal, + db_path, + self.inner.options.synchronous, + pfs.generation(), + )?; + let mut tx = pfs.begin_large(tx_id)?; + let mut staged: Vec = std::mem::take(&mut self.pending_facts) + .into_iter() + .zip(keep) + .filter_map(|(f, k)| k.then_some(f)) + .collect(); + let written = if staged.is_empty() { + Ok(()) + } else { + pfs.write_staged_chunk(&mut tx, &mut staged) + }; + drop(staged); + // After a failure the transaction stays open: `commit` refuses it + // (STG-046), and a rollback or drop discards it. + self.large = Some(tx); + written?; + match current { + Current::Small(facts) => self.write_statement(std::iter::once(Ok(facts))), + Current::Large(statement) => self.write_statement(statement.chunks()?), + } + } + + /// Write one statement of a large transaction a chunk at a time, under + /// a statement base (#550 spec §5): a rejected statement returns the + /// working trees to it and leaves the transaction usable. + #[cfg(not(target_arch = "wasm32"))] + fn write_statement(&mut self, chunks: impl IntoIterator>) -> Result<()> + where + C: std::ops::DerefMut, + { + use crate::storage::persistent_facts::ChunkError; + let (WriteContext::File { pfs, .. }, Some(tx)) = (&mut *self.guard, self.large.as_mut()) + else { + bail_coded!( + ErrorCode::Int019, + "a large statement without a large transaction" + ); + }; + pfs.begin_statement(tx); + for chunk in chunks { + let written = match chunk { + Ok(mut chunk) => pfs.write_large_chunk(tx, &mut chunk), + Err(e) => Err(ChunkError::Statement(e)), + }; + if let Err(ChunkError::Statement(e) | ChunkError::Failure(e)) = written { + // A failure has failed the handle already; the base is + // restored either way. + let _ = pfs.end_statement(tx, false); + return Err(e); + } + } + pfs.end_statement(tx, true) + } + + /// Discard the working state of a large transaction (#550 spec §4.4). + #[cfg(not(target_arch = "wasm32"))] + fn rollback_large(&mut self) { + if let (Some(tx), WriteContext::File { pfs, .. }) = (self.large.take(), &mut *self.guard) { + pfs.rollback_large(tx); + } + } + fn execute_rule_command( &self, rule: crate::query::datalog::types::Rule, @@ -1659,6 +1837,31 @@ impl<'a> WriteTransaction<'a> { } fn commit_inner(mut self) -> Result<()> { + #[cfg(not(target_arch = "wasm32"))] + if self.large.is_some() { + // A failed handle is refused; the drop rolls the transaction back. + refuse_if_failed(&self.guard)?; + // No statement wrote a fact: nothing to commit, no tx_count taken. + if !self.large.as_ref().is_some_and(|tx| tx.wrote()) { + self.rollback_large(); + } + if let ( + Some(tx), + WriteContext::File { + pfs, + wal, + db_path, + wal_entry_count, + }, + ) = (self.large.take(), &mut *self.guard) + { + pfs.commit_large(tx)?; + Minigraf::delete_wal(wal, db_path, wal_entry_count)?; + } + self.committed = true; + set_write_tx_active(false); + return Ok(()); + } let facts_to_commit = std::mem::take(&mut self.pending_facts); if !facts_to_commit.is_empty() { @@ -1756,44 +1959,28 @@ impl<'a> WriteTransaction<'a> { /// Explicitly roll back the transaction. Also happens implicitly on drop. pub fn rollback(mut self) { + #[cfg(not(target_arch = "wasm32"))] + self.rollback_large(); self.pending_facts.clear(); self.committed = true; // Suppress rollback in Drop set_write_tx_active(false); } - - /// Build a merged fact snapshot for transactional reads. - /// - /// Pending facts still carry `VALID_FROM_USE_TX_TIME` for assertions where no - /// explicit `valid_from` was supplied (the sentinel is left intact so `commit()` - /// can stamp it with the real commit timestamp). We resolve it here using each - /// fact's own staged `tx_id` so transactional queries see a coherent valid-time. - fn merged_query_facts(&self) -> Result> { - let committed = self.inner.fact_storage.get_all_facts()?; - let mut merged = - Vec::with_capacity(committed.len().saturating_add(self.pending_facts.len())); - merged.extend(committed); - merged.extend(self.pending_facts.iter().cloned().map(|mut f| { - if f.asserted && f.valid_from == VALID_FROM_USE_TX_TIME { - f.valid_from = f.tx_id.cast_signed(); - } - f - })); - Ok(Arc::from(merged)) - } - - /// Return the read-time floor implied by pending facts only. - fn pending_read_now_floor(&self) -> Option { - self.pending_facts - .iter() - .map(|fact| fact.tx_id.cast_signed()) - .max() - } } /// Keep, for each `(entity, attribute, value)`, only the staged records of /// the newest statement that wrote it (#477). Staged facts carry their /// statement's synthetic `tx_count`; the order of what is kept is unchanged. fn keep_last_statement(facts: Vec) -> Vec { + let keep = last_statement_mask(&facts); + facts + .into_iter() + .zip(keep) + .filter_map(|(fact, kept)| kept.then_some(fact)) + .collect() +} + +/// For each of `facts`, whether [`keep_last_statement`] keeps it. +fn last_statement_mask(facts: &[Fact]) -> Vec { use crate::storage::index::encode_value; use std::collections::HashMap; @@ -1805,18 +1992,13 @@ fn keep_last_statement(facts: Vec) -> Vec { .or_insert(fact.tx_count); *slot = (*slot).max(fact.tx_count); } - let keep: Vec = facts + facts .iter() .zip(&encoded) .map(|(fact, value)| { newest.get(&(&fact.entity, fact.attribute.as_str(), value.as_slice())) == Some(&fact.tx_count) }) - .collect(); - facts - .into_iter() - .zip(keep) - .filter_map(|(fact, kept)| kept.then_some(fact)) .collect() } @@ -1825,7 +2007,10 @@ impl Drop for WriteTransaction<'_> { if !self.committed { // Implicit rollback: pending facts are simply discarded. // No changes were made to the shared FactStorage during buffering, - // so no cleanup is required there. + // so no cleanup is required there. A large transaction's working + // pages are discarded (#550 spec §4.4). + #[cfg(not(target_arch = "wasm32"))] + self.rollback_large(); self.pending_facts.clear(); set_write_tx_active(false); } @@ -2385,6 +2570,7 @@ mod tests { synchronous: SyncMode::Full, read_only: false, query_memory_limit: usize::MAX, + transaction_chunk_facts: 65_536, }; let db = Minigraf::open_with_options(&path, opts).unwrap(); assert_eq!(db.inner.options.wal_checkpoint_threshold, 5); diff --git a/src/fault_matrix.rs b/src/fault_matrix.rs index dae29c54dc..30e8eb29d7 100644 --- a/src/fault_matrix.rs +++ b/src/fault_matrix.rs @@ -63,8 +63,9 @@ enum Op { /// A large transaction (#550): chunks written into working trees and /// committed as a checkpoint. `one_slot`: on a file never checkpointed, /// with one valid meta slot; else on the file `build` makes. `wal`: with - /// entries pending in the WAL beforehand, else with no WAL. - Large { one_slot: bool, wal: bool }, + /// entries pending in the WAL beforehand, else with no WAL. `tx`: as a + /// `WriteTransaction` of several statements (statement bases). + Large { one_slot: bool, wal: bool, tx: bool }, } impl Op { @@ -79,6 +80,7 @@ impl Op { /// The transaction the operation writes, and how many records it leaves. fn x(self) -> (&'static str, usize) { match self { + Op::Large { tx: true, .. } => (X_LARGE, X_TX_FACTS), Op::Large { .. } => (X_LARGE, X_LARGE_FACTS), _ => (X, X_FACTS), } @@ -98,6 +100,31 @@ const X_LARGE: &str = r#"(transact [[:x1 :p/x 1] [:x1 :p/x 2] [:x1 :p/x 3] const X_LARGE_FACTS: usize = 10; const LARGE_CHUNK: usize = 3; +/// A `WriteTransaction` around [`X_LARGE`]: a staged statement first, then, +/// after it, a statement that fails `API-011` after writing a chunk and one +/// that repeats and changes earlier statements' triples. It leaves +/// [`X_TX_FACTS`] records. +const X_TX_BEFORE: &str = "(transact [[:x1 :p/x 1] [:x9 :p/x 9]])"; +const X_TX_FAILS: &str = r#"(transact [[:x11 :p/x 1 {:valid-from "2020-01-01T00:00:00Z"}] + [:x12 :p/x 1] [:x13 :p/x 1] [:x11 :p/x 1 {:valid-from "2021-01-01T00:00:00Z"}]])"#; +const X_TX_AFTER: &str = + r#"(transact [[:x1 :p/x 2 {:valid-from "2020-01-01T00:00:00Z"}] [:x10 :p/x 10] [:x9 :p/x 9]])"#; +const X_TX_FACTS: usize = 12; + +/// Run the `WriteTransaction` of `Op::Large { tx: true, .. }`. +fn large_write_tx(db: &Minigraf) -> Result<(), crate::MinigrafError> { + let mut tx = db.begin_write()?; + tx.execute(X_TX_BEFORE)?; + tx.execute(X_LARGE)?; + match tx.execute(X_TX_FAILS) { + Err(e) if e.code() == "API-011" => {} + Err(e) => return Err(e), + Ok(_) => panic!("a statement with two windows of a triple was accepted"), + } + tx.execute(X_TX_AFTER)?; + tx.commit() +} + fn open(path: &Path, op: Op) -> Minigraf { let threshold = if op == Op::AutoCheckpoint { 3 } else { 1000 }; OpenOptions::new() @@ -133,6 +160,7 @@ fn build(path: &Path, op: Op) -> Minigraf { if let Op::Large { one_slot: true, wal, + .. } = op { if wal { @@ -214,10 +242,15 @@ fn run(op: Op, f: Fault) -> u64 { Op::Transact | Op::TransactNewWal | Op::AutoCheckpoint => { (db.execute(X).map(|_| ()), Some(db)) } - Op::Large { .. } => { + Op::Large { tx, .. } => { let _chunk = crate::query::datalog::parser::statement::set_tx_chunk_facts(Some(LARGE_CHUNK)); - (db.execute(X_LARGE).map(|_| ()), Some(db)) + let result = if tx { + large_write_tx(&db) + } else { + db.execute(X_LARGE).map(|_| ()) + }; + (result, Some(db)) } Op::Checkpoint => (db.checkpoint(), Some(db)), Op::Rebuild => (db.rebuild_indexes(), Some(db)), @@ -336,6 +369,7 @@ fn faults_during_a_large_transaction() { run_all(Op::Large { one_slot: false, wal: true, + tx: false, }); } @@ -344,6 +378,7 @@ fn faults_during_a_large_transaction_that_creates_the_wal() { run_all(Op::Large { one_slot: false, wal: false, + tx: false, }); } @@ -354,6 +389,7 @@ fn faults_during_a_large_transaction_on_a_new_file() { run_all(Op::Large { one_slot: true, wal: false, + tx: false, }); } @@ -362,6 +398,43 @@ fn faults_during_a_large_transaction_on_a_new_file_with_a_wal() { run_all(Op::Large { one_slot: true, wal: true, + tx: false, + }); +} + +#[test] +fn faults_during_a_large_write_transaction() { + run_all(Op::Large { + one_slot: false, + wal: true, + tx: true, + }); +} + +#[test] +fn faults_during_a_large_write_transaction_that_creates_the_wal() { + run_all(Op::Large { + one_slot: false, + wal: false, + tx: true, + }); +} + +#[test] +fn faults_during_a_large_write_transaction_on_a_new_file() { + run_all(Op::Large { + one_slot: true, + wal: false, + tx: true, + }); +} + +#[test] +fn faults_during_a_large_write_transaction_on_a_new_file_with_a_wal() { + run_all(Op::Large { + one_slot: true, + wal: true, + tx: true, }); } diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 192c84afcc..ef9b65a20b 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -70,6 +70,20 @@ impl PendingStore { true } + /// A store of `facts`, duplicates skipped: a `WriteTransaction`'s staged + /// facts for one query (#550 spec §7). + fn of(facts: Vec) -> Self { + let mut store = PendingStore { + facts: Vec::with_capacity(facts.len()), + keys: HashSet::new(), + indexes: Indexes::new(), + }; + for fact in facts { + store.push(fact); + } + store + } + /// Append `facts` without the duplicate check (fresh writes: each has a /// new tx_count, so none can repeat a stored one). fn extend(&mut self, facts: Vec) { @@ -155,11 +169,95 @@ pub(crate) struct Snapshot { _pin: Option>, pending: Arc>, pending_len: usize, + /// A `WriteTransaction`'s staged facts, read after the pending facts as + /// one store with them (#550 spec §7). Their `tx_count`s are above every + /// pending one. + staged: Option>, /// Wall-clock time when the snapshot was taken (Unix ms): the "now" of /// valid-time reads, so every fact in the snapshot was stamped by then. now: i64, } +/// The pending part of a snapshot: the first `len` facts of the pending store +/// at positions `0..len`, then the staged facts at `len..`. +struct PendingView<'a> { + p: &'a PendingStore, + len: usize, + staged: Option<&'a PendingStore>, +} + +impl<'a> PendingView<'a> { + fn total(&self) -> usize { + self.len + .saturating_add(self.staged.map_or(0, |s| s.facts.len())) + } + + fn fact(&self, pos: usize) -> Result { + match pos.checked_sub(self.len) { + None => pending_fact(self.p, pos), + Some(i) => match self.staged { + Some(s) => pending_fact(s, i), + None => Err(err_coded!(ErrorCode::Int045, pos)), + }, + } + } + + /// The facts at positions `from..to` (clamped), cloned onto `out`. + fn extend(&self, from: usize, to: usize, out: &mut Vec) { + let to = to.min(self.total()); + let first = self.p.facts.get(from.min(self.len)..to.min(self.len)); + out.extend_from_slice(first.unwrap_or(&[])); + if let Some(s) = self.staged { + let (from, to) = (from.saturating_sub(self.len), to.saturating_sub(self.len)); + out.extend_from_slice(s.facts.get(from.min(to)..to).unwrap_or(&[])); + } + } + + /// The EAVT entries from `from` on, of both stores in key order, with + /// their view positions. + fn eavt( + &self, + from: std::ops::Bound<&crate::storage::index::EavtKey>, + ) -> impl Iterator + use<'a> { + let range = (from, std::ops::Bound::Unbounded); + let staged = self.staged.map(|s| s.indexes.eavt.range(range)); + merged(self.len, self.p.indexes.eavt.range(range), staged) + } + + /// [`Self::eavt`] for AEVT. + fn aevt( + &self, + from: std::ops::Bound<&crate::storage::index::AevtKey>, + ) -> impl Iterator + use<'a> { + let range = (from, std::ops::Bound::Unbounded); + let staged = self.staged.map(|s| s.indexes.aevt.range(range)); + merged(self.len, self.p.indexes.aevt.range(range), staged) + } +} + +/// Merge one index of the pending store (positions below `len` only) and of +/// the staged facts (positions offset by `len`) in key order. +fn merged<'a, K: Ord + 'a>( + len: usize, + pending: impl Iterator, + staged: Option>, +) -> impl Iterator { + let mut a = pending + .filter(move |&(_, &pos)| pos < len) + .map(|(k, &pos)| (k, pos)) + .peekable(); + let mut b = staged + .into_iter() + .flatten() + .map(move |(k, &pos)| (k, pos.saturating_add(len))) + .peekable(); + std::iter::from_fn(move || match (a.peek(), b.peek()) { + (Some((ka, _)), Some((kb, _))) if kb < ka => b.next(), + (Some(_), _) => a.next(), + (None, _) => b.next(), + }) +} + impl std::fmt::Debug for Snapshot { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.debug_struct("Snapshot") @@ -170,9 +268,42 @@ impl std::fmt::Debug for Snapshot { } impl Snapshot { - /// The number of pending facts in the snapshot. + /// The number of pending facts in the snapshot, staged ones included. pub(crate) fn pending_len(&self) -> usize { self.pending_len + .saturating_add(self.staged.as_ref().map_or(0, |s| s.facts.len())) + } + + /// This snapshot with `facts` staged after its pending ones (#550 spec + /// §7), its `now` raised to the newest of their `tx_id`s. + pub(crate) fn with_staged(mut self, facts: Vec) -> Self { + if let Some(newest) = facts.iter().map(|f| f.tx_id.cast_signed()).max() { + self.now = self.now.max(newest); + self.staged = Some(Arc::new(PendingStore::of(facts))); + } + self + } + + /// This snapshot with `reader` as its committed facts and no pending ones: + /// a large transaction's working trees, which hold the pending store's + /// facts too (#550 spec §7). + #[cfg(not(target_arch = "wasm32"))] + pub(crate) fn with_committed( + mut self, + reader: Arc, + ) -> Self { + self.committed = Some(reader); + self.pending_len = 0; + self.staged = None; + self + } + + fn view<'a>(&'a self, p: &'a PendingStore) -> PendingView<'a> { + PendingView { + p, + len: self.pending_len.min(p.facts.len()), + staged: self.staged.as_deref(), + } } /// Wall-clock time when the snapshot was taken (Unix ms). @@ -199,8 +330,7 @@ impl Snapshot { /// no intermediate vector: the pending store can hold millions of facts. fn extend_with_pending(&self, from: usize, to: usize, facts: &mut Vec) -> Result<()> { let p = self.read_pending()?; - let to = to.min(self.pending_len).min(p.facts.len()); - facts.extend_from_slice(p.facts.get(from.min(to)..to).unwrap_or(&[])); + self.view(&p).extend(from, to, facts); Ok(()) } @@ -211,7 +341,7 @@ impl Snapshot { Some(reader) => reader.all_facts()?, None => Vec::new(), }; - self.extend_with_pending(0, self.pending_len, &mut all)?; + self.extend_with_pending(0, usize::MAX, &mut all)?; Ok(all) } @@ -235,9 +365,10 @@ impl Snapshot { as_of: Option, ) -> Result> { let p = self.read_pending()?; + let view = self.view(&p); let mut facts = Vec::new(); for &scan in scans { - pending_facts_of_scan(&p, self.pending_len, scan, as_of, &mut facts)?; + pending_facts_of_scan(&view, scan, as_of, &mut facts)?; if let Some(reader) = &self.committed { facts.extend(reader.live_facts(scan, as_of)?); } @@ -264,7 +395,7 @@ impl Snapshot { ) -> Result> { let p = self.read_pending()?; let mut facts = Vec::new(); - pending_facts_of_scan(&p, self.pending_len, scan, as_of, &mut facts)?; + pending_facts_of_scan(&self.view(&p), scan, as_of, &mut facts)?; Ok(facts) } @@ -287,11 +418,11 @@ impl Snapshot { ) -> Result { use crate::storage::Scan; use crate::storage::index::{AevtKey, EavtKey}; - use std::ops::Bound::{Excluded, Included, Unbounded}; + use std::ops::Bound::{Excluded, Included}; let p = self.read_pending()?; + let view = self.view(&p); let walk = RunWalk { - p: &p, - len: self.pending_len, + view: &view, as_of, max, }; @@ -302,7 +433,7 @@ impl Snapshot { _ => Included(AevtKey::attribute_start(attribute)), }; walk.run( - p.indexes.aevt.range((from, Unbounded)), + view.aevt(from.as_ref()), |k| k.attribute == attribute, |k| (&k.entity, k.attribute.as_str()), out, @@ -320,7 +451,7 @@ impl Snapshot { _ => Included(start), }; walk.run( - p.indexes.eavt.range((from, Unbounded)), + view.eavt(from.as_ref()), |k| match scan { Scan::Entity(e) => k.entity == *e, Scan::EntityAttribute(e, a) => k.entity == *e && k.attribute == a, @@ -340,8 +471,7 @@ impl Snapshot { /// One call of [`Snapshot::pending_live`] over one pending index. struct RunWalk<'a> { - p: &'a PendingStore, - len: usize, + view: &'a PendingView<'a>, as_of: Option, max: usize, } @@ -352,7 +482,7 @@ impl<'a> RunWalk<'a> { /// last run when it stopped early, `None` when the range is done. fn run( &self, - entries: impl Iterator, + entries: impl Iterator, in_range: impl Fn(&K) -> bool, run_of: impl Fn(&K) -> (&EntityId, &str), out: &mut Vec, @@ -361,7 +491,7 @@ impl<'a> RunWalk<'a> { let mut first: Option<&K> = None; let mut last: Option<&K> = None; let mut emitted = 0usize; - for (k, &pos) in entries { + for (k, pos) in entries { if !in_range(k) { break; } @@ -376,11 +506,9 @@ impl<'a> RunWalk<'a> { } first.get_or_insert(k); last = Some(k); - if pos < self.len { - let f = pending_fact(self.p, pos)?; - if self.as_of.is_none_or(|n| f.tx_count <= n) { - run.push(f); - } + let f = self.view.fact(pos)?; + if self.as_of.is_none_or(|n| f.tx_count <= n) { + run.push(f); } } flush_run(&mut run, out); @@ -687,6 +815,7 @@ impl FactStorage { .map(|_| Arc::new(self.pins.pin(d.generation))), pending: Arc::clone(&d.pending), pending_len, + staged: None, now, }) } @@ -767,7 +896,7 @@ impl FactStorage { /// Apply transaction-time snapshot semantics to a batch of facts. /// -/// Shared by `FactStorage::get_facts_as_of()` and transactional overlay reads. +/// Used by `Snapshot::facts_as_of`. pub(crate) fn filter_facts_as_of(facts: Vec, as_of: &AsOf) -> Vec { facts .into_iter() @@ -979,22 +1108,18 @@ impl FactStorage { } } -/// The pending facts of `scan` among the first `len` of `p`, up to `as_of`, -/// appended to `facts`. +/// The pending facts of `scan` in `view`, up to `as_of`, appended to `facts`. fn pending_facts_of_scan( - p: &PendingStore, - len: usize, + view: &PendingView<'_>, scan: crate::storage::Scan<'_>, as_of: Option, facts: &mut Vec, ) -> Result<()> { use crate::storage::Scan; use crate::storage::index::{AevtKey, EavtKey}; + use std::ops::Bound::Included; let mut push = |pos: usize| -> Result<()> { - if pos >= len { - return Ok(()); - } - let f = pending_fact(p, pos)?; + let f = view.fact(pos)?; if as_of.is_none_or(|n| f.tx_count <= n) { facts.push(f); } @@ -1002,12 +1127,12 @@ fn pending_facts_of_scan( }; match scan { Scan::All => { - for pos in 0..len.min(p.facts.len()) { + for pos in 0..view.total() { push(pos)?; } } Scan::Entity(entity) => { - for (key, &pos) in p.indexes.eavt.range(EavtKey::entity_start(*entity)..) { + for (key, pos) in view.eavt(Included(&EavtKey::entity_start(*entity))) { if key.entity != *entity { break; } @@ -1016,7 +1141,7 @@ fn pending_facts_of_scan( } Scan::EntityAttribute(entity, attribute) => { let start = EavtKey::entity_attribute_start(*entity, attribute); - for (key, &pos) in p.indexes.eavt.range(start..) { + for (key, pos) in view.eavt(Included(&start)) { if key.entity != *entity || key.attribute != attribute { break; } @@ -1024,7 +1149,7 @@ fn pending_facts_of_scan( } } Scan::Attribute(attribute) => { - for (key, &pos) in p.indexes.aevt.range(AevtKey::attribute_start(attribute)..) { + for (key, pos) in view.aevt(Included(&AevtKey::attribute_start(attribute))) { if key.attribute != attribute { break; } diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 29b8b6bc8d..42a0706420 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -147,8 +147,6 @@ pub struct DatalogExecutor { /// The state every read of this executor sees; when `None`, each read /// takes its own snapshot of `storage`. snapshot: Option, - facts_override: Option>, - read_now_floor: Option, rules: Arc>, // RwLock pre-wired for 7.7b register_aggregate API. functions: Arc>, @@ -164,8 +162,6 @@ impl DatalogExecutor { DatalogExecutor { storage, snapshot: None, - facts_override: None, - read_now_floor: None, rules: Arc::new(RwLock::new(RuleRegistry::new())), functions: Arc::new(RwLock::new(FunctionRegistry::with_builtins())), max_derived_facts: crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS, @@ -184,27 +180,6 @@ impl DatalogExecutor { DatalogExecutor { storage, snapshot: None, - facts_override: None, - read_now_floor: None, - rules, - functions, - max_derived_facts: crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS, - query_memory_limit: usize::MAX, - } - } - - /// Create a `DatalogExecutor` over a merged fact slice while sharing rules and functions. - pub(crate) fn new_from_facts_with_rules_and_functions( - facts: Arc<[Fact]>, - pending_read_now_floor: Option, - rules: Arc>, - functions: Arc>, - ) -> Self { - DatalogExecutor { - storage: FactStorage::new(), - snapshot: None, - facts_override: Some(facts), - read_now_floor: pending_read_now_floor, rules, functions, max_derived_facts: crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS, @@ -237,8 +212,6 @@ impl DatalogExecutor { DatalogExecutor { storage, snapshot: None, - facts_override: None, - read_now_floor: None, rules, functions, max_derived_facts, @@ -269,17 +242,12 @@ impl DatalogExecutor { } /// Read-time "now" for query visibility: the snapshot's time when the - /// executor has one, otherwise the wall clock. - /// - /// Overlay reads floor the wall clock to the newest staged fact so buffered - /// writes remain visible even if their synthetic metadata is slightly ahead - /// of the current millisecond. + /// executor has one, otherwise the wall clock. A write transaction's + /// snapshot is at or after its newest staged fact (#550 spec §7). fn read_now(&self) -> i64 { - let now = self - .snapshot + self.snapshot .as_ref() - .map_or_else(|| tx_id_now().cast_signed(), Snapshot::now); - self.read_now_floor.map_or(now, |floor| now.max(floor)) + .map_or_else(|| tx_id_now().cast_signed(), Snapshot::now) } /// Execute a Datalog command @@ -385,15 +353,11 @@ impl DatalogExecutor { fn filter_facts_for_query(&self, query: &DatalogQuery) -> Result> { let now = self.read_now(); - let source_facts: Vec = match (&self.facts_override, query.as_of.as_ref()) { - (Some(facts), Some(as_of)) => { - crate::graph::storage::filter_facts_as_of(facts.iter().cloned().collect(), as_of) - } - (Some(facts), None) => facts.iter().cloned().collect(), + let source_facts: Vec = match query.as_of.as_ref() { // A counter is a key bound, so committed history is cut on index keys. - (None, Some(AsOf::Counter(n))) => self.live_source_facts(query, Some(*n))?, - (None, Some(as_of)) => self.read_snapshot()?.facts_as_of(as_of)?, - (None, None) => self.live_source_facts(query, None)?, + Some(AsOf::Counter(n)) => self.live_source_facts(query, Some(*n))?, + Some(as_of) => self.read_snapshot()?.facts_as_of(as_of)?, + None => self.live_source_facts(query, None)?, }; let tx_filtered = source_facts; @@ -560,11 +524,8 @@ impl DatalogExecutor { // Check if query uses rules if query.uses_rules() { - // The engine runs the rule queries it plans (#548); reads inside - // a write transaction stay here (#550). - if self.facts_override.is_none() - && let Some(answer) = self.open_rule_query(&query)? - { + // The engine runs the rule queries it plans (#548). + if let Some(answer) = self.open_rule_query(&query)? { return Ok(answer); } // Use StratifiedEvaluator for queries with rule invocations (handles negation and strata) @@ -577,10 +538,7 @@ impl DatalogExecutor { } // The streaming engine runs the queries it has operators for (#473). - // Reads inside a write transaction (`facts_override`) stay here (#550). - if self.facts_override.is_none() - && let Some(plan) = crate::query::engine::plan(&query) - { + if let Some(plan) = crate::query::engine::plan(&query) { { let registry = self .functions @@ -706,8 +664,6 @@ impl DatalogExecutor { DatalogExecutor { storage: self.storage.clone(), snapshot: Some(snapshot), - facts_override: None, - read_now_floor: self.read_now_floor, rules: self.rules.clone(), functions: self.functions.clone(), max_derived_facts: self.max_derived_facts, diff --git a/src/query/datalog/parser/statement.rs b/src/query/datalog/parser/statement.rs index 5d5ced9bde..e5e14089f1 100644 --- a/src/query/datalog/parser/statement.rs +++ b/src/query/datalog/parser/statement.rs @@ -18,9 +18,16 @@ use crate::query::datalog::matcher::{edn_to_entity_id, edn_to_value}; use crate::query::datalog::types::{AttributeSpec, DatalogCommand, EdnValue, Pattern, Transaction}; use anyhow::Result; -/// Most facts a statement holds materialised at once; a statement with more -/// is read again in chunks of this many (spec §3.3). -const TX_CHUNK_FACTS: usize = 16_384; +/// The default of `OpenOptions::transaction_chunk_facts`: the most facts a +/// statement holds materialised at once; a statement with more is read again +/// in chunks of this many (spec §3.3), and a transaction with more is large +/// (§4). Set by measurement (#550 plan, PR 3 results) for speed: 16,384 took +/// up to twice as long with random entities, for 40–55 MiB less at 1M facts. +pub(crate) const DEFAULT_TX_CHUNK_FACTS: usize = 65_536; + +/// The largest chunk: a small transaction is one WAL entry, and replay +/// refuses an entry of more facts than this (`wal.rs`, #686). +pub(crate) const MAX_TX_CHUNK_FACTS: usize = 1_000_000; #[cfg(any(test, feature = "test-oracle"))] thread_local! { @@ -29,7 +36,7 @@ thread_local! { static HELD: std::cell::Cell<(usize, usize)> = const { std::cell::Cell::new((0, 0)) }; } -/// Set this thread's chunk size (`None`: [`TX_CHUNK_FACTS`]), so tests reach +/// Set this thread's chunk size (`None`: the database's), so tests reach /// pass 2 and the large path with small statements. #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn set_tx_chunk_facts(n: Option) -> TxChunkGuard { @@ -59,12 +66,14 @@ pub(crate) fn take_held_high_water() -> usize { }) } -pub(crate) fn tx_chunk_facts() -> usize { +/// The chunk size for a database configured with `configured`: this +/// thread's test setting if any, kept between 1 and [`MAX_TX_CHUNK_FACTS`]. +pub(crate) fn tx_chunk_facts(configured: usize) -> usize { #[cfg(any(test, feature = "test-oracle"))] if let Some(n) = CHUNK_FACTS.with(std::cell::Cell::get) { - return n.max(1); + return n.clamp(1, MAX_TX_CHUNK_FACTS); } - TX_CHUNK_FACTS + configured.clamp(1, MAX_TX_CHUNK_FACTS) } /// At most one chunk of a statement's materialised facts. With `test` or @@ -501,10 +510,15 @@ pub(crate) struct Statement<'a> { } /// Pass 1 over the statement `input` of kind `kind`: phases 1–6, with -/// `tx_id` as the time an unset `valid_from` takes. A phase 1–4 error is -/// returned here; a phase 5–6 one by [`Statement::facts`]. -pub(crate) fn read_statement(input: &str, kind: Kind, tx_id: TxId) -> Result> { - let chunk = tx_chunk_facts(); +/// `tx_id` as the time an unset `valid_from` takes, keeping at most `chunk` +/// facts (from [`tx_chunk_facts`]). A phase 1–4 error is returned here; a +/// phase 5–6 one by [`Statement::facts`]. +pub(crate) fn read_statement( + input: &str, + kind: Kind, + tx_id: TxId, + chunk: usize, +) -> Result> { let mut kept: Vec = Vec::new(); let mut last_end = 0usize; let mut resume = None; @@ -682,7 +696,8 @@ mod tests { /// The write path through the statement reader. fn new_write(input: &str, kind: Kind, tx_id: TxId) -> Result> { - let facts = read_statement(input, kind, tx_id)?.facts()?; + let facts = + read_statement(input, kind, tx_id, tx_chunk_facts(DEFAULT_TX_CHUNK_FACTS))?.facts()?; check_valid_windows(&facts, tx_id)?; check_one_window_per_triple(&facts)?; Ok(facts) @@ -884,7 +899,13 @@ mod tests { let input = "(transact [[:a :n 1] [:a :n 2] [:a :n 3] [:a :n 4] [:a :n 5]])"; let statement = { let _chunk = set_tx_chunk_facts(Some(2)); - read_statement(input, Kind::Transact, 1).unwrap() + read_statement( + input, + Kind::Transact, + 1, + tx_chunk_facts(DEFAULT_TX_CHUNK_FACTS), + ) + .unwrap() }; assert_eq!(statement.kept.len(), 2, "kept facts"); let resume = statement.resume.expect("large"); @@ -908,7 +929,13 @@ mod tests { let exact = { let _chunk = set_tx_chunk_facts(Some(5)); - read_statement(input, Kind::Transact, 1).unwrap() + read_statement( + input, + Kind::Transact, + 1, + tx_chunk_facts(DEFAULT_TX_CHUNK_FACTS), + ) + .unwrap() }; assert!(exact.resume.is_none(), "five facts fit a chunk of five"); assert_eq!(exact.facts().unwrap().len(), 5, "facts"); @@ -920,19 +947,30 @@ mod tests { let input = format!("(transact [{input}])"); let _chunk = set_tx_chunk_facts(Some(3)); let _ = take_held_high_water(); - let statement = read_statement(&input, Kind::Transact, 1).unwrap(); + let statement = read_statement( + &input, + Kind::Transact, + 1, + tx_chunk_facts(DEFAULT_TX_CHUNK_FACTS), + ) + .unwrap(); let mut n = 0; for chunk in statement.chunks().unwrap() { n += chunk.unwrap().len(); } assert_eq!(n, 10); assert_eq!(take_held_high_water(), 3, "one chunk at a time"); - let held: Vec = read_statement(&input, Kind::Transact, 1) - .unwrap() - .chunks() - .unwrap() - .map(Result::unwrap) - .collect(); + let held: Vec = read_statement( + &input, + Kind::Transact, + 1, + tx_chunk_facts(DEFAULT_TX_CHUNK_FACTS), + ) + .unwrap() + .chunks() + .unwrap() + .map(Result::unwrap) + .collect(); assert_eq!(held.len(), 4); assert_eq!(take_held_high_water(), 10, "every chunk kept is counted"); drop(held); @@ -947,7 +985,13 @@ mod tests { let input = "(transact [[:a :n 1] [:a :n 2] [:a :n 3]])"; let statement = { let _chunk = set_tx_chunk_facts(Some(1)); - read_statement(input, Kind::Transact, 1).unwrap() + read_statement( + input, + Kind::Transact, + 1, + tx_chunk_facts(DEFAULT_TX_CHUNK_FACTS), + ) + .unwrap() }; let short = &input[..input.len() - 8]; let mut chunks = Chunks { @@ -965,17 +1009,28 @@ mod tests { #[test] fn materialisation_and_window_errors_come_with_the_facts() { let code = |r: Result>| MinigrafError::from(r.unwrap_err()).code(); - let statement = - read_statement("(transact [[1 :b 1]])", Kind::Transact, 1).expect("phases 1-4 pass"); + let statement = read_statement( + "(transact [[1 :b 1]])", + Kind::Transact, + 1, + tx_chunk_facts(DEFAULT_TX_CHUNK_FACTS), + ) + .expect("phases 1-4 pass"); assert_eq!(code(statement.facts()), "INT-002"); let statement = read_statement( "(transact [[:a :b 1 {:valid-to \"2001-01-01T00:00:00Z\"}]])", Kind::Transact, crate::graph::types::tx_id_now(), + tx_chunk_facts(DEFAULT_TX_CHUNK_FACTS), ) .expect("phases 1-4 pass"); assert_eq!(code(statement.facts()), "API-019"); - let shape = read_statement("(transact [[:a :b]])", Kind::Transact, 1); + let shape = read_statement( + "(transact [[:a :b]])", + Kind::Transact, + 1, + tx_chunk_facts(DEFAULT_TX_CHUNK_FACTS), + ); assert_eq!( MinigrafError::from(shape.err().expect("phase 4")).code(), "PRS-046" diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index d474f6bc59..77f2ba5a2e 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -1812,7 +1812,10 @@ fn rule_query_routing() { tx.execute("(query [:find ?x ?y :where (reach ?x ?y)])") .unwrap(); tx.rollback(); - assert_eq!(runs(), before, "a write transaction reads on the executor"); + assert!( + runs() > before, + "a write transaction reads on the engine (#550 spec §7)" + ); } /// The relations a rule query derives are read after the committed and diff --git a/src/storage/btree.rs b/src/storage/btree.rs index adde52e41f..2df9f55f79 100644 --- a/src/storage/btree.rs +++ b/src/storage/btree.rs @@ -567,6 +567,37 @@ pub fn collect_leaf_pages( Ok(leaves) } +/// The ids of every node of the tree at `root` (none for root 0), so a tree +/// that only one statement used can give its pages back (#550). +#[cfg(not(target_arch = "wasm32"))] +pub fn tree_pages(root: u64, backend: &dyn StorageBackend, cache: &PageCache) -> Result> { + let mut out = Vec::new(); + let mut stack = if root == 0 { + vec![] + } else { + vec![(root, 0usize)] + }; + while let Some((page_id, depth)) = stack.pop() { + 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(page_id, backend)?; + out.push(page_id); + match page.first().copied() { + Some(PAGE_TYPE_LEAF) => {} + Some(PAGE_TYPE_INTERNAL) => { + let children = Internal::new(&page[..])?.children()?; + stack.extend(children.into_iter().map(|c| (c, depth + 1))); + } + _ => bail_coded!(ErrorCode::Stg013, page_id), + } + } + Ok(out) +} + /// One internal node on the cursor's path from the root. struct Frame { page: Arc>, @@ -1708,6 +1739,28 @@ mod tests { cow_check(&committed, &committed[5..50], &mut rng); } + #[cfg(not(target_arch = "wasm32"))] + #[test] + fn tree_pages_lists_every_node_a_tree_reaches() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(64); + let mut alloc = PageAllocator::new(Vec::new(), 2, 1); + assert!(tree_pages(0, &backend, &cache).unwrap().is_empty()); + let mut freed = Vec::new(); + let entries: Vec = (0..3000).map(|n| entry(n, n)).collect(); + let root = cow_insert(0, entries, &mut backend, &cache, &mut alloc, &mut freed).unwrap(); + let more: Vec = (3000..3100).map(|n| entry(n, n)).collect(); + let root = cow_insert(root, more, &mut backend, &cache, &mut alloc, &mut freed).unwrap(); + let mut nodes = Vec::new(); + collect_leaf_pages(root, &backend, &cache, Some(&mut nodes)).unwrap(); + assert!(nodes.len() > 3, "a tree of more than one level"); + let mut got = tree_pages(root, &backend, &cache).unwrap(); + got.sort_unstable(); + nodes.sort_unstable(); + assert_eq!(got, nodes); + assert!(got.iter().all(|id| !freed.contains(id)), "no replaced page"); + } + #[test] fn cow_insert_into_root_zero_is_a_bulk_build() { let mut backend = MemoryBackend::new(); diff --git a/src/storage/node.rs b/src/storage/node.rs index 66eaa99772..0a30c06bf3 100644 --- a/src/storage/node.rs +++ b/src/storage/node.rs @@ -431,7 +431,7 @@ impl<'a> Internal<'a> { } /// All children in key order, `rightmost_child` last. - #[cfg(test)] + #[cfg(any(test, not(target_arch = "wasm32")))] pub fn children(&self) -> Result> { (0..=self.count).map(|i| self.child(i)).collect() } diff --git a/src/storage/page.rs b/src/storage/page.rs index 26b57aad03..5efaf04b20 100644 --- a/src/storage/page.rs +++ b/src/storage/page.rs @@ -190,6 +190,9 @@ pub struct PageAllocator { generation: u64, /// Every id handed out since [`tracking`](Self::tracking), when on. handed: Option>, + /// The ids handed out since [`begin_base`](Self::begin_base) and not + /// released again, when on (#550 spec §5.1). + since: Option>, } impl PageAllocator { @@ -208,6 +211,7 @@ impl PageAllocator { next_append, generation, handed: None, + since: None, } } @@ -225,6 +229,7 @@ impl PageAllocator { next_append, generation, handed: None, + since: None, } } @@ -264,9 +269,33 @@ impl PageAllocator { /// out again, [`finish_free_list`](Self::finish_free_list) lists it free. #[cfg(not(target_arch = "wasm32"))] pub fn release(&mut self, id: u64) { + if let Some(s) = self.since.as_mut() { + s.remove(&id); + } self.free.push(id); } + /// Record, from now on, the ids handed out and not released again: a + /// statement's base (#550 spec §5.1). Replaces any set already recording. + #[cfg(not(target_arch = "wasm32"))] + pub fn begin_base(&mut self) { + self.since = Some(std::collections::HashSet::new()); + } + + /// Whether `id` was handed out since [`begin_base`](Self::begin_base) and + /// not released since. + #[cfg(not(target_arch = "wasm32"))] + pub fn handed_since(&self, id: u64) -> bool { + self.since.as_ref().is_some_and(|s| s.contains(&id)) + } + + /// Stop recording and return the ids [`handed_since`](Self::handed_since) + /// held. + #[cfg(not(target_arch = "wasm32"))] + pub fn end_base(&mut self) -> std::collections::HashSet { + self.since.take().unwrap_or_default() + } + /// The generation every page written through this allocator is stamped with. #[cfg(test)] pub fn generation(&self) -> u64 { @@ -291,9 +320,7 @@ impl PageAllocator { self.skipped.push(id); continue; } - if let Some(h) = self.handed.as_mut() { - h.insert(id); - } + self.record(id); return Ok(id); } if self.chain_next == 0 { @@ -322,10 +349,17 @@ impl PageAllocator { self.next_append = id .checked_add(1) .ok_or_else(|| err_coded!(ErrorCode::Int048, "page id overflow"))?; + self.record(id); + Ok(id) + } + + fn record(&mut self, id: u64) { if let Some(h) = self.handed.as_mut() { h.insert(id); } - Ok(id) + if let Some(s) = self.since.as_mut() { + s.insert(id); + } } /// Free ids not handed out, in hand-out order. Chain pages not read yet and @@ -562,6 +596,27 @@ mod tests { ); } + #[cfg(not(target_arch = "wasm32"))] + #[test] + fn handed_since_covers_ids_after_begin_base_until_released() { + let b = crate::storage::backend::MemoryBackend::new(); + let c = crate::storage::cache::PageCache::new(0); + let mut a = PageAllocator::new(vec![3, 4], 10, 2).tracking(); + let before = a.alloc(&b, &c).unwrap(); + a.begin_base(); + let free = a.alloc(&b, &c).unwrap(); + let appended = a.alloc_append().unwrap(); + let released = a.alloc(&b, &c).unwrap(); + a.release(released); + assert!(!a.handed_since(before), "handed out before the base"); + assert!(a.handed_since(free) && a.handed_since(appended)); + assert!(!a.handed_since(released), "released again"); + assert!(a.handed(released), "still in the transaction's set"); + let since = a.end_base(); + assert_eq!(since, [free, appended].into_iter().collect()); + assert!(!a.handed_since(free), "no base after end_base"); + } + #[cfg(not(target_arch = "wasm32"))] #[test] fn a_released_id_not_handed_out_again_stays_free() { diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index d5ee113f44..783c4f3dd6 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -30,7 +30,7 @@ mod browser_access; #[cfg(not(target_arch = "wasm32"))] mod large_tx; #[cfg(not(target_arch = "wasm32"))] -pub(crate) use large_tx::ChunkError; +pub(crate) use large_tx::{ChunkError, LargeTx}; use std::sync::{Arc, Mutex}; /// Persistent fact storage with page-based persistence. diff --git a/src/storage/persistent_facts/large_tx.rs b/src/storage/persistent_facts/large_tx.rs index 30500e6516..8a5e5992b1 100644 --- a/src/storage/persistent_facts/large_tx.rs +++ b/src/storage/persistent_facts/large_tx.rs @@ -13,7 +13,7 @@ use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::graph::storage::{check_one_window_per_triple, check_valid_windows}; use crate::graph::types::{Fact, TxId}; use crate::storage::StorageBackend; -use crate::storage::btree::{LeafCursor, cow_update}; +use crate::storage::btree::{self, LeafCursor, cow_update}; use crate::storage::cache::PageCache; use crate::storage::dict::{DictReader, Encoded, Encoder}; use crate::storage::keys::{self, Index, KeyFact}; @@ -22,6 +22,7 @@ use crate::storage::node::Entry; use crate::storage::page::PageAllocator; use anyhow::Result; use std::collections::HashSet; +use std::sync::Arc; /// A large transaction in progress: generation `g`'s meta, the working state /// that becomes `g + 1`'s, and the pages it has written. @@ -36,6 +37,34 @@ pub(crate) struct LargeTx { freed: Vec, tx_count: u64, tx_id: TxId, + /// The pending store's facts written as the first chunk (plan decision + /// 27): the number of them the commit publishes. + pending_len: usize, + /// Whether a statement of the transaction is in the working trees: until + /// then every key of this `tx_count` is the current statement's (spec + /// §5.2 fast path). + written: bool, + /// The running statement's base, in a `WriteTransaction` (plan decision 33). + stmt: Option, +} + +/// A statement's base (spec §5.1, plan decision 28): what a failed statement +/// returns to. The ids handed out since are the allocator's +/// [`handed_since`](PageAllocator::handed_since) set. +struct Base { + /// The working roots, counters and fact count when the statement started. + work: MetaPage, + /// `freed`'s length then: pages of `g` the statement replaced are + /// referenced again by the restored roots (plan decision 31). + freed_len: usize, + /// Pages the base references that the statement replaced. + held: Vec, + /// Root of the claims tree: the triples whose base keys the statement + /// deleted (plan decision 30). + claims: u64, + /// Whether the statement wrote a fact (a statement with none, like a + /// rejected one, leaves the transaction as it was). + wrote: bool, } /// How a chunk failed. @@ -54,15 +83,23 @@ impl LargeTx { pub(crate) fn tx_id(&self) -> TxId { self.tx_id } + + /// Whether a statement wrote facts into the working trees. A transaction + /// with none commits nothing and takes no `tx_count`, as a small one. + pub(crate) fn wrote(&self) -> bool { + self.written + } } impl PersistentFactStorage { /// Make the current transaction large (spec §4.1 steps 2–4): raise the - /// cache's generation bound to `g + 1`, reserve the next `tx_count`, and - /// build the allocator. The caller has created the WAL guard (step 1). + /// cache's generation bound to `g + 1`, reserve the next `tx_count`, build + /// the allocator, and write the pending store's facts into the working + /// trees (plan decision 27). The caller has created the WAL guard (step 1). /// /// The `tx_count` is the next one; it is allocated at the commit point, - /// so a transaction that rolls back takes none (plan decision 14). + /// so a transaction that rolls back takes none (plan decision 14). An + /// error writing the pending facts fails the handle (`STG-046`). pub(crate) fn begin_large(&mut self, tx_id: TxId) -> Result { self.refuse_if_failed()?; let base = self.meta; @@ -81,7 +118,7 @@ impl PersistentFactStorage { .with_quarantine(self.storage.pages_in_force()) .tracking(); self.page_cache.set_generation_bound(next); - Ok(LargeTx { + let mut tx = LargeTx { base, work: MetaPage { generation: next, @@ -91,7 +128,102 @@ impl PersistentFactStorage { freed: Vec::new(), tx_count, tx_id, - }) + pending_len: 0, + written: false, + stmt: None, + }; + // No fact joins the pending store while the write lock is held, so + // these are the facts the commit publishes. Their own tx_counts and + // statement rules: only encoded and inserted. + let mut pending = self.storage.get_pending_facts(); + tx.pending_len = pending.len(); + if let Err(ChunkError::Statement(e) | ChunkError::Failure(e)) = + self.apply_chunk(&mut tx, &mut pending, false) + { + self.failed = true; + self.rollback_large(tx); + return Err(e); + } + Ok(tx) + } + + /// Write a `WriteTransaction`'s staged statements, reduced to the last + /// statement of each triple, as one chunk with no base (plan decision 26). + /// They passed every statement check, so any error fails the handle. + pub(crate) fn write_staged_chunk( + &mut self, + tx: &mut LargeTx, + facts: &mut [Fact], + ) -> Result<()> { + match self.write_large_chunk(tx, facts) { + Ok(()) => { + tx.written = true; + Ok(()) + } + Err(ChunkError::Statement(e) | ChunkError::Failure(e)) => { + self.failed = true; + Err(e) + } + } + } + + /// Start a statement of a large `WriteTransaction` (spec §5.1): record + /// its base. + pub(crate) fn begin_statement(&self, tx: &mut LargeTx) { + tx.alloc.begin_base(); + tx.stmt = Some(Base { + work: tx.work, + freed_len: tx.freed.len(), + held: Vec::new(), + claims: 0, + wrote: false, + }); + } + + /// End the running statement (spec §5.3). On success its base is dropped, + /// and the pages the base held and the claims tree are released. On + /// failure the working trees, counters and `freed` return to the base, + /// every page the statement wrote is released, and the held ones stay in + /// use. A failure here fails the handle. + pub(crate) fn end_statement(&mut self, tx: &mut LargeTx, ok: bool) -> Result<()> { + let Some(base) = tx.stmt.take() else { + return Ok(()); + }; + let since = tx.alloc.end_base(); + if ok { + let claims = { + let backend = self.lock()?; + btree::tree_pages(base.claims, &*backend, &self.page_cache) + }; + let claims = claims.inspect_err(|_| self.failed = true)?; + for id in claims.into_iter().chain(base.held) { + tx.alloc.release(id); + } + tx.written |= base.wrote; + } else { + tx.work = base.work; + tx.freed.truncate(base.freed_len); + for id in since { + tx.alloc.release(id); + } + } + Ok(()) + } + + /// A reader of the working trees, for a query inside the transaction + /// (spec §7): every committed fact, the pending store's, and the finished + /// statements'. Its own dictionary cache, so the committed reader's never + /// learns an id that is not committed. Unpinned: nothing frees a working + /// page while the transaction holds the write lock. + pub(crate) fn large_reader(&self, tx: &LargeTx) -> Arc { + Arc::new(crate::storage::reader::OnDiskReader::new( + self.backend.clone(), + self.page_cache.clone(), + &MetaPage { + last_checkpointed_tx_count: tx.tx_count, + ..tx.work + }, + )) } /// Write one chunk of the statement (spec §4.2): check it, stamp it with @@ -125,9 +257,10 @@ impl PersistentFactStorage { result } - /// Commit the transaction as a checkpoint (spec §4.3): the pending store's - /// facts join the working trees, the free list is written, and the meta - /// page of `g + 1` is the commit point. The caller deletes the WAL next. + /// Commit the transaction as a checkpoint (spec §4.3): the free list is + /// written, and the meta page of `g + 1` is the commit point; the pending + /// store's facts joined the working trees in [`Self::begin_large`]. The + /// caller deletes the WAL next. /// /// On an error the handle is failed (`STG-046`) and the in-memory state is /// rolled back; the file holds `g`, or `g + 1` complete if the meta page @@ -149,15 +282,9 @@ impl PersistentFactStorage { } fn commit_large_inner(&mut self, tx: &mut LargeTx) -> Result<()> { - let mut pending = self.storage.get_pending_facts(); - let pending_len = pending.len(); - // Their own tx_counts and statement rules: only encoded and inserted. - match self.apply_chunk(tx, &mut pending, false) { - Ok(()) => {} - Err(ChunkError::Statement(e) | ChunkError::Failure(e)) => return Err(e), + if tx.stmt.is_some() { + bail_coded!(ErrorCode::Int049, "commit inside a statement"); } - drop(pending); - let mut backend = self.lock()?; let (freelist_head, freelist_count, _) = tx.alloc @@ -189,7 +316,7 @@ impl PersistentFactStorage { self.storage.publish( reader, new_meta.generation, - pending_len, + tx.pending_len, std::mem::take(&mut tx.freed), ); Ok(()) @@ -214,9 +341,10 @@ impl PersistentFactStorage { } /// Encode `facts` against the working dictionary and apply them to the - /// working trees. With `own`, they are this transaction's: a fact an - /// earlier chunk wrote is kept once, and another window of one of its - /// triples is `API-011`. + /// working trees. With `own`, they are this transaction's (spec §5.2): a + /// fact the statement already wrote is kept once, another window of one + /// of its triples is `API-011`, and an earlier statement's keys of a + /// triple it writes are deleted. fn apply_chunk( &mut self, tx: &mut LargeTx, @@ -234,19 +362,56 @@ impl PersistentFactStorage { next_eid, next_iid, } = encoded; + let mut deletes: [Vec>; 4] = Default::default(); + let mut claims = Vec::new(); + if own && let Some(stmt) = tx.stmt.as_mut() { + stmt.wrote |= !facts.is_empty(); + } if own { - let repeats = repeats(&tx.work, &index[0], tx.tx_count, &*backend, cache)?; - drop_repeats(&mut index, &repeats).map_err(failure)?; + // Without a base, or before any statement is in the working + // trees, every key of this tx_count is the statement's. + let base = match &tx.stmt { + Some(b) if tx.written => Some((b.work.eavt_root, b.claims)), + _ => None, + }; + let r = resolve(&tx.work, base, &index[0], tx.tx_count, &*backend, cache)?; + drop_repeats(&mut index, &r.repeats).map_err(failure)?; + deletes = index_deletes(r.deletes).map_err(failure)?; + claims = r.claims; } let added = u64::try_from(index[0].len()) .map_err(|_| ChunkError::Failure(err_coded!(ErrorCode::Stg024)))?; + let deleted = u64::try_from(deletes[0].len()) + .map_err(|_| ChunkError::Failure(err_coded!(ErrorCode::Stg024)))?; let mut roots = tx.work.tree_roots(); - for (root, entries) in roots.iter_mut().zip(index.into_iter().chain([dict])) { + let deletes = deletes.into_iter().chain([Vec::new()]); + for ((root, entries), dels) in roots + .iter_mut() + .zip(index.into_iter().chain([dict])) + .zip(deletes) + { let mut replaced = Vec::new(); *root = cow_update( *root, entries, + dels, + &mut *backend, + cache, + &mut tx.alloc, + &mut replaced, + ) + .map_err(failure)?; + tx.replaced(replaced); + } + if !claims.is_empty() + && let Some(stmt) = tx.stmt.as_mut() + { + let mut replaced = Vec::new(); + let entries = claims.into_iter().map(|t| (t, Vec::new())).collect(); + stmt.claims = cow_update( + stmt.claims, + entries, Vec::new(), &mut *backend, cache, @@ -254,18 +419,17 @@ impl PersistentFactStorage { &mut replaced, ) .map_err(failure)?; - // A page this transaction wrote is referenced by nothing now; a - // page of `g` is freed at commit (spec §4.2 step 3; no statement - // base in a one-statement transaction, plan decision 13). - for id in replaced { - if tx.alloc.handed(id) { - tx.alloc.release(id); - } else { - tx.freed.push(id); - } - } + tx.replaced(replaced); } let [eavt_root, aevt_root, avet_root, vaet_root, dict_root] = roots; + let fact_count = tx + .work + .fact_count + .checked_add(added) + .and_then(|n| n.checked_sub(deleted)) + .ok_or_else(|| { + ChunkError::Failure(err_coded!(ErrorCode::Int048, "fact_count overflow")) + })?; tx.work = MetaPage { eavt_root, aevt_root, @@ -274,15 +438,34 @@ impl PersistentFactStorage { dict_root, next_eid, next_iid, - fact_count: tx.work.fact_count.checked_add(added).ok_or_else(|| { - ChunkError::Failure(err_coded!(ErrorCode::Int048, "fact_count overflow")) - })?, + fact_count, ..tx.work }; Ok(()) } } +impl LargeTx { + /// Account for the pages a `cow_update` replaced (spec §4.2 step 3). With + /// a base: written since it, released; not written by this transaction + /// (generation `g` references it), freed at commit; otherwise held by the + /// base. Without one, a page this transaction wrote is referenced by + /// nothing now (plan decision 13). + fn replaced(&mut self, replaced: Vec) { + for id in replaced { + if !self.alloc.handed(id) { + self.freed.push(id); + } else if let Some(stmt) = self.stmt.as_mut() + && !self.alloc.handed_since(id) + { + stmt.held.push(id); + } else { + self.alloc.release(id); + } + } + } +} + /// A chunk's statement checks, before it writes anything (plan decision 18): /// valid windows at the fixed `tx_id` (`API-019`), one window per triple /// within the chunk (`API-011`), and the sizes a checkpoint can store @@ -317,19 +500,39 @@ fn encode( encoder.finish(alloc, backend, cache) } -/// The positions in `eavt` (a chunk's sorted EAVT entries, all of `tx_count`) -/// of facts an earlier chunk of the transaction already wrote to the working -/// trees of `work` (#550 spec §5.2, fast path). Another window of an asserted -/// triple there is `API-011`, as within one statement today. -fn repeats( +/// What a chunk's records do to the working trees (spec §5.2). +struct Resolved { + /// Positions in the chunk's EAVT entries of facts the statement already + /// wrote: not inserted again. + repeats: Vec, + /// Earlier statements' EAVT keys of triples the chunk writes, sorted. + deletes: Vec>, + /// Those triples (EAVT key prefixes), sorted: they join the claims. + claims: Vec>, +} + +/// Resolve the records of a chunk (`eavt`: its sorted EAVT entries, all of +/// `tx_count`) against the working trees of `work` (spec §5.2, plan decision +/// 30). For each triple, its working keys of `tx_count` are the current +/// statement's when `base` is `None` (the fast path), when the triple is in +/// the claims (`base.1`), or when the first of them is not in the base's EAVT +/// tree (`base.0`); a fact the statement wrote is kept once, and another +/// window of an asserted triple is `API-011`, as within one statement today. +/// Otherwise they are earlier statements': deleted, and the triple is claimed. +fn resolve( work: &MetaPage, + base: Option<(u64, u64)>, eavt: &[Entry], tx_count: u64, backend: &dyn StorageBackend, cache: &PageCache, -) -> std::result::Result, ChunkError> { +) -> std::result::Result { let failure = ChunkError::Failure; - let mut out = Vec::new(); + let mut out = Resolved { + repeats: Vec::new(), + deletes: Vec::new(), + claims: Vec::new(), + }; if work.eavt_root == 0 { return Ok(out); } @@ -338,9 +541,11 @@ fn repeats( // triple, read once even when the chunk has several records of it. let mut start: Vec = Vec::new(); let mut run: Vec> = Vec::new(); + let mut earlier = false; for (i, (key, _)) in eavt.iter().enumerate() { let triple = keys::triple_len(Index::Eavt, key).map_err(failure)?; - let mut s = key.get(..triple).unwrap_or_default().to_vec(); + let t = key.get(..triple).unwrap_or_default(); + let mut s = t.to_vec(); keys::put_tx_desc(&mut s, tx_count); if s != start { start = s; @@ -362,10 +567,24 @@ fn repeats( run.push(k.clone()); cursor.next_ref().map_err(failure)?; } + earlier = match (base, run.first()) { + (Some((base_eavt, claims)), Some(first)) => { + !in_tree(claims, t, backend, cache).map_err(failure)? + && in_tree(base_eavt, first, backend, cache).map_err(failure)? + } + _ => false, + }; + if earlier { + out.deletes.append(&mut run); + out.claims.push(t.to_vec()); + } + } + if earlier { + continue; } let asserted = key.last() == Some(&1); if run.iter().any(|k| k == key) { - out.push(i); + out.repeats.push(i); } else if asserted && run.iter().any(|k| k.last() == Some(&1)) { let attribute = KeyFact::decode(Index::Eavt, key) .and_then(|kf| DictReader::new(work.dict_root, backend, cache).name_of(kf.a)) @@ -379,6 +598,29 @@ fn repeats( Ok(out) } +/// Whether the tree at `root` (0: none) holds `key`. +fn in_tree(root: u64, key: &[u8], backend: &dyn StorageBackend, cache: &PageCache) -> Result { + Ok(root != 0 && btree::get(root, key, backend, cache)?.is_some()) +} + +/// The keys of the four index trees for sorted EAVT keys `eavt`, each sorted +/// and distinct. +fn index_deletes(eavt: Vec>) -> Result<[Vec>; 4]> { + let mut out: [Vec>; 4] = Default::default(); + for key in &eavt { + let kf = KeyFact::decode(Index::Eavt, key)?; + for (v, idx) in out.iter_mut().zip(Index::ALL).skip(1) { + v.extend(kf.key(idx)); + } + } + for v in out.iter_mut().skip(1) { + v.sort_unstable(); + v.dedup(); + } + out[0] = eavt; + Ok(out) +} + /// Remove the facts at `positions` of the EAVT entries from all four index /// trees' entries. fn drop_repeats(index: &mut [Vec; 4], positions: &[usize]) -> Result<()> { @@ -524,6 +766,365 @@ mod tests { } } + fn outcome(r: Result) -> String { + match r { + Ok(_) => "ok".into(), + Err(e) => e.code().to_string(), + } + } + + /// The statements of a `WriteTransaction` that statement bases decide: + /// repeats and other windows of earlier statements' facts within and + /// across chunks, retract-then-assert and assert-then-retract, failing + /// statements, and a repeat of the first statement. + fn tx_workload() -> Vec { + let w = workload(); + vec![ + w[0].clone(), + // Statement 1's `[:a :n 2]` again, then another window of it in + // a later chunk: API-011 (plan decision 30, the claims case). + format!( + r#"(transact [[:a :n 2] [:b :ref :a] [:c :s "{LONG}"] + [:a :n 2 {{:valid-from "2020-01-01T00:00:00Z"}}]])"# + ), + "(retract [[:a :n 1] [:d :k :kw]])".into(), + "(transact [[:a :n 1] [:x :n 1] [:y :n 1]])".into(), + "(transact [[:z :n 1] [:z :n 2] [:z :n 3]])".into(), + "(retract [[:z :n 2] [:z :n 9] [:a :n 2]])".into(), + // Another window of an earlier statement's fact: the last wins. + r#"(transact [[:a :n 3 {:valid-from "2022-01-01T00:00:00Z"}] [:b :s "short"] [:e :n 1]])"#.into(), + // API-011 within one statement, in a later chunk. + r#"(transact [[:f :n 1 {:valid-from "2020-01-01T00:00:00Z"}] [:g :n 1] [:h :n 1] + [:f :n 1 {:valid-from "2021-01-01T00:00:00Z"}]])"# + .into(), + w[0].clone(), + w[3].clone(), + w[5].clone(), + w[6].clone(), + ] + } + + /// Run `stmts` in one `WriteTransaction` and commit; each statement's + /// outcome. + fn run_tx(db: &Minigraf, stmts: &[String]) -> Vec { + let mut tx = db.begin_write().unwrap(); + let out = stmts.iter().map(|s| outcome(tx.execute(s))).collect(); + tx.commit().unwrap(); + out + } + + #[test] + fn large_write_transactions_store_what_small_ones_do() { + let dir = tempfile::tempdir().unwrap(); + let stmts = tx_workload(); + let (left, right) = stmts.split_at(5); + // One transaction of every statement, then two transactions with a + // committed and a pending statement between them. + let script = |db: &Minigraf| -> Vec { + let mut out = run_tx(db, &stmts); + out.extend(run_tx(db, left)); + db.execute("(transact [[:a :n 7] [:p :n 1]])").unwrap(); + db.checkpoint().unwrap(); + db.execute("(transact [[:a :n 8] [:p :n 2]])").unwrap(); + out.extend(run_tx(db, right)); + out + }; + let small = Minigraf::open(dir.path().join("small.graph")).unwrap(); + let want_outcomes = script(&small); + assert!(want_outcomes.iter().filter(|o| *o == "API-011").count() >= 2); + let want = records(&small); + + for chunk in 1..=4 { + let path = dir.path().join(format!("large{chunk}.graph")); + let db = Minigraf::open(&path).unwrap(); + let outcomes = { + let _chunk = set_tx_chunk_facts(Some(chunk)); + script(&db) + }; + assert_eq!(outcomes, want_outcomes, "outcomes at chunk {chunk}"); + assert!(records(&db) == want, "records at chunk {chunk}"); + assert_eq!(db.current_tx_count(), small.current_tx_count()); + assert!(db.verify().unwrap().is_ok(), "verify at chunk {chunk}"); + drop(db); + let db = Minigraf::open(&path).unwrap(); + assert!( + records(&db) == want, + "records after reopen at chunk {chunk}" + ); + assert!(db.verify().unwrap().is_ok()); + } + } + + const IN_TX_QUERIES: [&str; 5] = [ + "(query [:find ?e ?a ?v :where [?e ?a ?v]])", + "(query [:find ?v :where [:a :n ?v]])", + "(query [:find ?e ?v :any-valid-time :where [?e :n ?v]])", + "(query [:find ?e ?v :as-of 1 :where [?e :n ?v]])", + "(query [:find (count ?e) :where [?e :n _] (not [?e :ref _])])", + ]; + + fn query_rows(r: crate::QueryResult) -> Vec { + match r { + crate::QueryResult::QueryResults { results, .. } => { + let mut v: Vec = results.iter().map(|r| format!("{r:?}")).collect(); + v.sort(); + v + } + _ => panic!("not query results"), + } + } + + /// [`IN_TX_QUERIES`] inside one transaction, after each statement. + fn tx_reads(db: &Minigraf, stmts: &[String]) -> Vec>> { + let mut tx = db.begin_write().unwrap(); + let mut out = Vec::new(); + for stmt in stmts { + let _ = tx.execute(stmt); + out.push( + IN_TX_QUERIES + .iter() + .map(|q| query_rows(tx.execute(q).unwrap())) + .collect(), + ); + } + tx.rollback(); + out + } + + #[test] + fn queries_inside_a_transaction_see_what_its_commit_would_hold() { + let dir = tempfile::tempdir().unwrap(); + let setup = |db: &Minigraf| { + db.execute("(transact [[:a :n 1] [:z :n 2] [:k :n 5]])") + .unwrap(); + db.checkpoint().unwrap(); + // Pending: a retraction and an assertion the transaction changes. + db.execute("(retract [[:k :n 5]])").unwrap(); + db.execute("(transact [[:a :n 9]])").unwrap(); + }; + let mut stmts = tx_workload(); + stmts.insert(1, "(transact [[:k :n 5]])".into()); + stmts.insert(2, "(retract [[:a :n 9]])".into()); + // After each statement: what a commit of the statements so far holds. + let want: Vec>> = (1..=stmts.len()) + .map(|n| { + let db = Minigraf::in_memory().unwrap(); + setup(&db); + run_tx(&db, &stmts[..n]); + IN_TX_QUERIES + .iter() + .map(|q| query_rows(db.execute(q).unwrap())) + .collect() + }) + .collect(); + for chunk in [None, Some(1), Some(2), Some(3), Some(4)] { + let db = Minigraf::open(dir.path().join(format!("t{chunk:?}.graph"))).unwrap(); + setup(&db); + let got = { + let _chunk = set_tx_chunk_facts(chunk); + tx_reads(&db, &stmts) + }; + assert_eq!(got.len(), want.len()); + for (i, (g, w)) in got.iter().zip(&want).enumerate() { + assert!(g == w, "reads after statement {i} at chunk {chunk:?}"); + } + } + } + + /// Spec §5.3 and plan decision 31: a statement that replaces pages of + /// `g` and then fails leaves them referenced by the restored trees, so + /// they must not be freed at commit. + #[test] + fn a_failed_statement_gives_back_the_pages_of_g_it_replaced() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + let db = Minigraf::open(&path).unwrap(); + let bulk: String = (0..400) + .map(|i| format!(r#"[:e{i} :n {i}] [:e{i} :s "value {i}"]"#)) + .collect(); + db.execute(&format!("(transact [{bulk}])")).unwrap(); + db.checkpoint().unwrap(); + let w1 = r#"{:valid-from "2020-01-01T00:00:00Z"}"#; + let w2 = r#"{:valid-from "2021-01-01T00:00:00Z"}"#; + let _chunk = set_tx_chunk_facts(Some(2)); + let mut tx = db.begin_write().unwrap(); + tx.execute("(transact [[:e1 :n 10] [:e2 :n 20] [:e3 :n 30]])") + .unwrap(); + for i in [150, 250, 350] { + let err = tx + .execute(&format!( + "(transact [[:e{i} :n 1 {w1}] [:e{i} :t 1] [:e{i} :u 1] [:e{i} :n 1 {w2}]])" + )) + .unwrap_err(); + assert_eq!(err.code(), "API-011"); + } + tx.execute("(transact [[:e399 :n 0] [:e398 :n 0] [:e397 :n 0]])") + .unwrap(); + tx.commit().unwrap(); + assert!(db.verify().unwrap().is_ok(), "no page in use is free"); + for i in 0..5 { + db.execute(&format!("(transact [[:e{} :n -1] [:f{i} :n 1]])", i * 90)) + .unwrap(); + db.checkpoint().unwrap(); + } + assert!(db.verify().unwrap().is_ok(), "no page handed out twice"); + } + + #[test] + fn a_rolled_back_large_write_transaction_leaves_the_file_as_it_was() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + let db = Minigraf::open(&path).unwrap(); + db.execute(&workload()[0]).unwrap(); + db.checkpoint().unwrap(); + db.execute("(transact [[:h :n 1]])").unwrap(); + let before = records(&db); + let generation = db.generation(); + { + let _chunk = set_tx_chunk_facts(Some(2)); + let mut tx = db.begin_write().unwrap(); + for stmt in tx_workload() { + let _ = tx.execute(&stmt); + } + drop(tx); + } + assert!(records(&db) == before); + assert_eq!(db.generation(), generation, "no meta written"); + assert!(wal_of(&path).exists(), "the WAL guard stays"); + db.checkpoint().unwrap(); + assert_eq!(db.generation(), generation + 1); + assert!(records(&db) == before); + assert!(db.verify().unwrap().is_ok(), "every page accounted for"); + drop(db); + let db = Minigraf::open(&path).unwrap(); + assert!(records(&db) == before); + } + + /// Spec §4.1 step 5: a staged window that has ended when the transaction + /// becomes large rejects the statement that makes it large, and the + /// transaction stays small. + #[test] + fn a_staged_window_ended_at_the_switch_rejects_the_statement() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + let db = Minigraf::open(&path).unwrap(); + let _chunk = set_tx_chunk_facts(Some(2)); + let mut tx = db.begin_write().unwrap(); + // Timestamps are whole seconds: one to two seconds from now. + let ends = (crate::graph::types::tx_id_now().cast_signed() / 1000 + 2) * 1000; + let ends_text = crate::temporal::millis_to_timestamp_string(ends).unwrap(); + tx.execute(&format!( + r#"(transact [[:a :n 1 {{:valid-to "{ends_text}"}}]])"# + )) + .unwrap(); + while crate::graph::types::tx_id_now().cast_signed() <= ends { + std::thread::sleep(std::time::Duration::from_millis(20)); + } + let err = tx.execute("(transact [[:b :n 1] [:c :n 1]])").unwrap_err(); + assert_eq!(err.code(), "API-019"); + assert!(!wal_of(&path).exists(), "nothing to undo: no WAL guard"); + // Still small and usable: a one-fact statement is staged. + tx.execute("(transact [[:d :n 1]])").unwrap(); + assert_eq!(tx.commit().unwrap_err().code(), "API-019"); + assert!(records(&db).is_empty()); + } + + /// A large transaction whose statements all failed commits nothing and + /// takes no `tx_count`, as a small one with nothing staged. + #[test] + fn a_large_write_transaction_with_no_statement_takes_no_tx_count() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + let db = Minigraf::open(&path).unwrap(); + db.execute("(transact [[:a :n 1]])").unwrap(); + let before = records(&db); + let _chunk = set_tx_chunk_facts(Some(2)); + let mut tx = db.begin_write().unwrap(); + let stmt = r#"(transact [[:b :n 1 {:valid-from "2020-01-01T00:00:00Z"}] [:c :n 1] + [:d :n 1] [:b :n 1 {:valid-from "2021-01-01T00:00:00Z"}]])"#; + assert_eq!(tx.execute(stmt).unwrap_err().code(), "API-011"); + assert!(wal_of(&path).exists()); + tx.commit().unwrap(); + assert_eq!(db.current_tx_count(), 1); + assert!(records(&db) == before); + db.checkpoint().unwrap(); + assert!(db.verify().unwrap().is_ok()); + } + + #[test] + fn a_failed_handle_is_refused_when_a_transaction_would_become_large() { + use crate::storage::fault::{self, Fault}; + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("t.graph")).unwrap(); + db.execute("(transact [[:a :n 1]])").unwrap(); + fault::arm(Fault::Eio, 0); + db.checkpoint().expect_err("the checkpoint fails"); + fault::disarm(); + let _chunk = set_tx_chunk_facts(Some(2)); + let mut tx = db.begin_write().unwrap(); + tx.execute("(transact [[:b :n 1]])").unwrap(); + let err = tx.execute("(transact [[:c :n 1] [:d :n 1]])").unwrap_err(); + assert_eq!(err.code(), "STG-046"); + assert_eq!(tx.commit().unwrap_err().code(), "STG-046"); + } + + #[test] + fn a_failure_in_a_large_write_transaction_fails_its_commit() { + use crate::storage::fault::{self, Fault}; + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + let db = Minigraf::open(&path).unwrap(); + db.execute(&workload()[0]).unwrap(); + db.checkpoint().unwrap(); + let before = records(&db); + let _chunk = set_tx_chunk_facts(Some(2)); + let mut tx = db.begin_write().unwrap(); + tx.execute("(transact [[:b :n 1] [:c :n 1] [:d :n 1]])") + .unwrap(); + fault::arm(Fault::Eio, 0); + tx.execute("(transact [[:e :n 1] [:f :n 1] [:g :n 1]])") + .expect_err("a page write fails"); + fault::disarm(); + assert_eq!(tx.commit().unwrap_err().code(), "STG-046"); + db.kill(); + let db = Minigraf::open(&path).unwrap(); + assert!(records(&db) == before); + assert!(db.verify().unwrap().is_ok()); + } + + /// `OpenOptions::transaction_chunk_facts` sets the chunk size, kept + /// between 1 and the most facts a WAL entry holds. + #[test] + fn the_chunk_size_is_an_open_option() { + use crate::query::datalog::parser::statement::{ + DEFAULT_TX_CHUNK_FACTS, MAX_TX_CHUNK_FACTS, tx_chunk_facts, + }; + assert_eq!(OpenOptions::default().transaction_chunk_facts, 65_536); + assert_eq!(DEFAULT_TX_CHUNK_FACTS, 65_536); + assert_eq!(tx_chunk_facts(0), 1); + assert_eq!(tx_chunk_facts(usize::MAX), MAX_TX_CHUNK_FACTS); + assert_eq!(MAX_TX_CHUNK_FACTS, crate::wal::MAX_FACTS_PER_ENTRY); + let dir = tempfile::tempdir().unwrap(); + for (chunk, large) in [(2, true), (3, false), (0, true)] { + let path = dir.path().join(format!("t{chunk}.graph")); + let db = OpenOptions::new() + .transaction_chunk_facts(chunk) + .path(&path) + .open() + .unwrap(); + db.execute("(transact [[:a :n 1] [:b :n 2] [:c :n 3]])") + .unwrap(); + // A large statement commits as a checkpoint and deletes the WAL. + assert_eq!(!wal_of(&path).exists(), large, "chunk {chunk}"); + let mut tx = db.begin_write().unwrap(); + tx.execute("(transact [[:d :n 1] [:e :n 2]])").unwrap(); + tx.execute("(transact [[:f :n 1] [:g :n 2]])").unwrap(); + tx.commit().unwrap(); + assert_eq!(records(&db).len(), 7); + assert!(db.verify().unwrap().is_ok()); + } + } + #[test] fn a_large_statement_returns_its_tx_id_and_answers_as_of() { let dir = tempfile::tempdir().unwrap(); diff --git a/src/wal.rs b/src/wal.rs index 98a37961ec..ab6619915b 100644 --- a/src/wal.rs +++ b/src/wal.rs @@ -37,6 +37,11 @@ use std::fs::{File, OpenOptions}; use std::io::{self, Read, Seek, SeekFrom, Write}; use std::path::Path; +/// The most facts replay reads from one entry; a larger count is taken as +/// damage. A small transaction is one entry of at most +/// `OpenOptions::transaction_chunk_facts` facts, which is kept below this. +pub(crate) const MAX_FACTS_PER_ENTRY: usize = 1_000_000; + const WAL_MAGIC: [u8; 4] = *b"MWAL"; const WAL_VERSION: u32 = 2; /// Format v7 (Minigraf v2.x) WAL version, read as base generation 1. @@ -451,7 +456,6 @@ fn scan_entries(file: &mut File) -> Result<(Vec, u64)> { .map_err(|_| err_coded!(ErrorCode::Wal005))?; // Sanity cap: no legitimate entry has more than 1M facts - const MAX_FACTS_PER_ENTRY: usize = 1_000_000; if num_facts > MAX_FACTS_PER_ENTRY { break; // treat as corrupt entry } diff --git a/tests/crash_kill_test.rs b/tests/crash_kill_test.rs index ee78556cab..44e9030dfd 100644 --- a/tests/crash_kill_test.rs +++ b/tests/crash_kill_test.rs @@ -24,7 +24,10 @@ //! With the `test-oracle` feature a sixth variant makes most transactions //! large (#550): they write pages and commit as a checkpoint, with no WAL //! entry, and every fourth one is followed by a large statement that fails -//! after writing pages and rolls back. The kill lands during a large +//! after writing pages and rolls back. Every third runs as a +//! `WriteTransaction` of three statements: the opposite of the transaction, +//! that failing statement, then the transaction itself, which the last +//! statement decides (statement bases). The kill lands during a large //! transaction, after its commit point, or after a rollback before the next //! checkpoint. //! @@ -178,9 +181,10 @@ enum Variant { AutoCheckpoint, /// As `CheckpointEvery3`, with `SyncMode::Normal` (no WAL fsync). NormalSync, - /// Statements of more than [`LARGE_CHUNK`] facts are large (#550), and a - /// failing large statement follows every fourth transaction; - /// `checkpoint()` after every fifth. + /// Statements of more than [`LARGE_CHUNK`] facts are large (#550), a + /// failing large statement follows every fourth transaction, every third + /// is a `WriteTransaction` ([`in_write_tx`]); `checkpoint()` after every + /// fifth. #[cfg(feature = "test-oracle")] Large, } @@ -204,6 +208,25 @@ const LARGE_CHUNK: usize = 2; const FAILS_LARGE: &str = r#"(transact [[:e0 :a0 0 {:valid-from "2020-01-01T00:00:00Z"}] [:e1 :a0 0] [:e2 :a0 0] [:e0 :a0 0 {:valid-from "2021-01-01T00:00:00Z"}]])"#; +/// Run `stmt` as a `WriteTransaction` with the same result: the opposite +/// statement over the same triples, [`FAILS_LARGE`] (rejected, the +/// transaction stays usable), then `stmt`, which wins every triple. +#[cfg(feature = "test-oracle")] +fn in_write_tx(db: &Minigraf, stmt: &str) { + let opposite = match stmt.strip_prefix("(transact ") { + Some(rest) => format!("(retract {rest}"), + None => stmt.replacen("(retract ", "(transact ", 1), + }; + let mut tx = db.begin_write().expect("child begin_write"); + tx.execute(&opposite).expect("child statement"); + let e = tx + .execute(FAILS_LARGE) + .expect_err("a failing large statement"); + assert_eq!(e.code(), "API-011"); + tx.execute(stmt).expect("child statement"); + tx.commit().expect("child commit"); +} + impl Variant { fn options(self) -> OpenOptions { let opts = OpenOptions::new(); @@ -481,6 +504,13 @@ fn crash_kill_child_entrypoint() { let mut live = BTreeSet::new(); for k in 1.. { let (stmt, next) = next_tx(&mut rng, &live); + #[cfg(feature = "test-oracle")] + if large && k % 3 == 0 { + in_write_tx(&db, &stmt); + } else { + db.execute(&stmt).expect("child transaction"); + } + #[cfg(not(feature = "test-oracle"))] db.execute(&stmt).expect("child transaction"); log.write_all(format!("{k}\n").as_bytes()) .expect("child logs transaction"); diff --git a/tests/large_transaction_acceptance_test.rs b/tests/large_transaction_acceptance_test.rs index cfb31468f0..336f94c369 100644 --- a/tests/large_transaction_acceptance_test.rs +++ b/tests/large_transaction_acceptance_test.rs @@ -17,8 +17,8 @@ use minigraf::{Minigraf, QueryResult}; const FACTS: usize = 1_000_000; -/// `TX_CHUNK_FACTS` until #550 PR 3's measurement sets it. -const TX_CHUNK_FACTS: usize = 16_384; +/// The default `OpenOptions::transaction_chunk_facts`. +const TX_CHUNK_FACTS: usize = 65_536; /// A `kB` field of `/proc/self/status`; 0 where it does not exist. fn proc_status_kb(field: &str) -> usize { diff --git a/tests/memory_limit_test.rs b/tests/memory_limit_test.rs index 7f6733aa63..a43db36375 100644 --- a/tests/memory_limit_test.rs +++ b/tests/memory_limit_test.rs @@ -110,11 +110,10 @@ fn the_database_answers_after_qry_012() { assert_eq!(rows(result), 1, "a small query still runs"); } -/// A query inside a write transaction that has staged writes runs on the -/// executor, which does not count yet (#549 spec §2); before any write it -/// runs on the engine and is counted. +/// A query inside a write transaction runs on the engine and is counted, +/// before and after a staged write (#550 spec §7). #[test] -fn write_transactions_with_staged_writes_are_not_counted_yet() { +fn write_transaction_queries_are_counted() { let db = db(0); let mut tx = db.begin_write().unwrap(); assert_eq!( @@ -122,7 +121,10 @@ fn write_transactions_with_staged_writes_are_not_counted_yet() { "QRY-012" ); tx.execute("(transact [[:p50 :age 50]])").unwrap(); - assert_eq!(rows(tx.execute(QUERY).unwrap()), 51); + assert_eq!( + tx.execute(QUERY).expect_err("a staged write").code(), + "QRY-012" + ); tx.rollback(); } diff --git a/tests/model_based_test.proptest-regressions b/tests/model_based_test.proptest-regressions index f0818d1258..9b185b1056 100644 --- a/tests/model_based_test.proptest-regressions +++ b/tests/model_based_test.proptest-regressions @@ -5,3 +5,4 @@ # It is recommended to check this file in to source control so that # everyone who runs the test benefits from these saved cases. cc ae0b4b21bae878a9b766b323137bb385a1736529adf2fa100ca840d3f378eaa3 # shrinks to steps = [Step { op: WriteTx { stmts: [Retract { facts: [(0, 0, Int(0))] }, Transact { window: Window { vf: None, vt: None }, facts: [FactSpec { e: 0, a: 0, v: Int(0), window: Window { vf: None, vt: None } }] }], commit: true }, probe: Probe { as_of: 0, at: 0, e: 0, a: 0, v: Int(0) } }] +cc a1c3a24395aa628ce0c750b09737fa21067cea17b22d8f091b066b0f5764607f # shrinks to steps = [Step { op: WriteTx { stmts: [Transact { window: Window { vf: None, vt: None }, facts: [FactSpec { e: 0, a: 0, v: Int(0), window: Window { vf: Some(0), vt: None } }, FactSpec { e: 0, a: 0, v: Int(0), window: Window { vf: None, vt: None } }, FactSpec { e: 0, a: 0, v: Int(0), window: Window { vf: None, vt: None } }] }], commit: true }, probe: Probe { as_of: 0, at: 0, e: 0, a: 0, v: Int(0), pick: 0 } }]