diff --git a/CHANGELOG.md b/CHANGELOG.md index a1fde70b14..94519de939 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -57,6 +57,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **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). - **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. - **Committed reads hide superseded history on index keys** (#379). A query's committed facts are now reduced to the ones that survive net-assert (each fact's assertion from its newest transaction, unless that transaction retracted it; #435) while walking the index keys, before any fact is built. Only surviving entries are decoded and translated through the dictionary. A transaction that retracted a triple hides everything older in it, and a long run of hidden entries is skipped with one `seek`. `:as-of N` point and attribute queries now take the same index path instead of reading every fact in the file. On a checkpointed file with 2,000 superseded values, a point query takes 1.03 ms instead of 4.61 ms, an attribute scan 1.24 ms instead of 5.87 ms, and an `:as-of` point query 23 µs instead of 5.6 ms (at depth 1). Results are unchanged: the executor still applies net-assert to committed and pending facts together, and a pending fact is always newer than a committed one. - **B+tree reads no longer follow leaf sibling links** (v8 storage format, PR 1 of 5; #374). Every index scan uses a cursor that walks down from the root and keeps the path, with a forward `seek` that climbs only as far as needed. This prepares for copy-on-write index pages, which cannot keep sibling links. The file format and query results are unchanged. Concurrent 100k-fact scans take 25–37 % less time and checkpointing after one fact at 10k facts 9 % less; single point lookups and attribute scans are 2–6 % slower (about 0.4 µs per lookup). A corrupted child pointer now fails with STG-013 (wrong page type) or INT-049 (cycle) instead of following a bad link. diff --git a/CLAUDE.md b/CLAUDE.md index 8c43ed576d..82dd7ecadb 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -139,14 +139,14 @@ cargo run < demos/demo_negation.txt - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute` - `magic_sets.rs`: Magic-sets rewriting for demand-driven recursive rule evaluation (not applied to rules with `not`/`not-join`) -3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: one pattern, then per-fact pseudo-attribute patterns on its entity and expression clauses in `optimizer::plan` order, plain `:find` variables, today), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs), `filter.rs` (`Filter`/`Bind` and pseudo-attribute columns over batches), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids), `project.rs` (ids → values for returned rows only), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree). `DatalogExecutor::execute_query` tries it first. +3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: one pattern, then per-fact pseudo-attribute patterns on its entity and expression clauses in `optimizer::plan` order, plain `:find` variables, today), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs), `filter.rs` (`Filter`/`Bind` and pseudo-attribute columns over batches), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids), `project.rs` (ids → values for returned rows only), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree). `mod.rs`: `Operator` (`next_batch`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` try it first: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) 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`) - - `src/cursor.rs`: `Cursor` / `Batch` — owned, `Send` cursor returned by `Minigraf::query` and `PreparedQuery::query` (#432); answer computed at open today, shaped for streaming operators; holds a `Snapshot` (one state of the store, its committed generation pinned, #543) until dropped + - `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) @@ -204,7 +204,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1481 tests** (1471 passing, 10 ignored; unit + integration + doc). +**1489 tests** (1479 passing, 10 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/README.md b/README.md index 2c20ab8e26..1d2caea753 100644 --- a/README.md +++ b/README.md @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1481 tests +cargo test # run 1489 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/ROADMAP.md b/ROADMAP.md index ddc6090ace..a3b8863be2 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -93,7 +93,7 @@ Scope — format and storage integrity: Scope — query API: -- Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`, with the current evaluator computing the answer at open). The binding cursor objects follow. Streaming operators replace the evaluator behind the cursor in 3.x without further API changes; how operators bound their memory (spill, scratch pages in the `.graph` file, or a clear error) is still open. +- Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) produces rows as they are pulled for the queries it runs (one pattern with expressions and pseudo-attributes, #544); joins, negation, aggregates, rules and transaction reads move to it in #545–#551, without API changes. Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549). - Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log pins its generation: checkpoints run but do not reuse its pages (#543; `API-013` deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462. - Read-only open: `OpenOptions::read_only` takes a shared lock, so several readers can hold a file at once, writes nothing to the file or its WAL (a WAL is applied in memory, a v7 file is read without migrating), and refuses writes with `API-014` (#429; Rust API done on `v3`). The bindings' `open_with_options` follows. - Raw log writer: `LogWriter` builds a new database from `FactRecord`s with their `tx_count`, `tx_id`, valid-time windows and assertion flags kept, gaps allowed (a purged transaction stays a hole for `:as-of`), at `.partial` renamed into place by `finish` (#431; Rust API done on `v3`). Completes extract (#429, #430), transform, load. The binding objects follow. diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index 6db0a8e0ab..fb21656560 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -85,7 +85,20 @@ The harness builds with `--profile envelope`: `release` at opt-level 3, which is - **Bindings as `HashMap` (about 25%).** SipHash insert, lookup and drop per row; #473's columnar batches replace them. - **`net_asserted_facts` over committed facts that `live_facts` already resolved (about 10%)** (#532). - **Keyword constants hashed to a UUID per fact (about 8% of the join)** (#531). -- `attribute_value` reads the whole attribute instead of seeking AVET (#518). +- `attribute_value` reads the whole attribute instead of seeking AVET (#518). Fixed by the streaming engine's `Scan` (#544): see below. + +### Streaming engine (#544) + +Single-pattern queries run on the streaming engine since #544 (with expressions and pseudo-attributes since its second PR); a cursor pulls one batch of up to 1,024 rows at a time. A/B on an otherwise idle two-socket server, each run pinned to its own NUMA node, base and change on different sockets and swapped between rounds; `v3` before #544 PR 3 (ce2e320) against #544 PR 3, two rounds each, p50 shown (the table above is an older run on a different machine). + +| Shape | 100K | 1M | 10M | +|---|---:|---:|---:| +| `attribute_value` p50 (both sides, since PR 1) | 24 µs | 22 µs | 22 µs | +| `attribute_scan` p50, `v3` → PR 3 | 24.0 → 23.2 ms | 268 → 248 ms | 3.12 → 2.59 s | +| `attribute_scan` peak RSS, `v3` → PR 3 | 11 → 6 MiB | 58 → 7 MiB | 458 → 7 MiB | +| point, `:as-of`, `:valid-at`, hot entity | unchanged (16–26 µs; hot 0.3 ms) | unchanged | unchanged | + +`attribute_value` reads only the AVET range of its value since #544 PR 1 (#518): 22–24 µs at every scale here, where the table above, before #544, has 24.5 ms, 288 ms and 3.16 s. An attribute scan drained with `next_batch(1000)` now holds one batch: peak RSS no longer grows with the number of rows (1.67M rows at 10M facts in 7 MiB, against a 4 MiB baseline). Before PR 3 the cursor held the whole answer, and in PR 3's first commit the query's id cache still held every entity it returned (189 MiB at 10M). Joins, aggregates and rules still run on the executor and are unchanged (#545–#548). ### Python FFI round trip diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index aa3eb30c33..c2a8ec6bc5 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-14 with `cargo test --quiet` -**Result**: 1,471 passing tests and 10 ignored tests (1,481 total) +**Result**: 1,479 passing tests and 10 ignored tests (1,489 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). @@ -14,7 +14,7 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Multi-value and index-key correctness** (`tests/multi_value_test.rs`, 10 tests): same-transaction multi-valued facts surviving query-time dedup, retracting several values of one attribute in one call, valid-time stints (facts differing only in valid time), maximum-value-size boundaries, and format v8 index keys (value bytes + assert/retract flag) (#287, #371). - **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration (including v7→v8 index rebuild and v1–v6 rejection via `STG-028`), WAL replay, checksums, corruption handling, and fault injection. - **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, SIGKILL recovery, and queries seeing each concurrent transaction whole and reading one state for all their patterns, including while a checkpoint runs (`tests/snapshot_atomicity_test.rs`, #554, #555, #558). Generation pins (#543): a pinned generation's pages are never written by later saves or index rebuilds and are reused once the pin is dropped (by page id, `storage::persistent_facts`, `storage::pins`, `storage::page`); fact logs stay correct while checkpoints, rebuilds and concurrent writers run, and see whole transactions only (`tests/fact_log_test.rs`). Query and prepared-query cursors keep their answer and their pages across writes, checkpoints and index rebuilds, and the file stops growing once they close (`tests/cursor_test.rs`); a snapshot leaves out facts appended after it on every scan (`graph::storage`); a crash at every write point of a save with a pinned generation loses no fact and no page, and the reopened database reuses the quarantined ids (`storage::persistent_facts`); the browser withholds free pages a pinned generation may read and releases them once out of force (`storage::pins::split_released`, and a `#[wasm_bindgen_test]` with an open `BrowserDb` cursor). -- **Streaming query engine** (#473, #544): every query the engine runs is also run by the existing executor under `cfg(test)` and the `test-oracle` feature, and the answers must agree (`query::engine::oracle`); CI runs the whole suite with the feature, so the model-based, property, golden-corpus and integration suites check the engine. `query::engine::tests` reaches every index choice, net-assert of pending records over committed ones, `:as-of`, valid time, long strings and reads of several batches, in memory, across checkpoints and after reopen, expression filters and bindings (including rebinding and failing expressions), pseudo-attribute columns, keyword/UUID/float constants against keywords, refs and UUID-named keywords, and checks which queries stay on the executor and that INT-026 and QRY-007 come first. Resumed `live_keys` reads equal one live read over random histories (`storage::persistent_facts`). +- **Streaming query engine** (#473, #544): every query the engine runs is also run by the existing executor under `cfg(test)` and the `test-oracle` feature, and the answers must agree (`query::engine::oracle`); CI runs the whole suite with the feature, so the model-based, property, golden-corpus and integration suites check the engine. `query::engine::tests` reaches every index choice, net-assert of pending records over committed ones, `:as-of`, valid time, long strings and reads of several batches, in memory, across checkpoints and after reopen, expression filters and bindings (including rebinding and failing expressions), pseudo-attribute columns, keyword/UUID/float constants against keywords, refs and UUID-named keywords, and checks which queries stay on the executor and that INT-026 and QRY-007 come first. Resumed `live_keys` reads equal one live read over random histories (`storage::persistent_facts`). Lazy cursors (`cursor::tests`, #544 PR 3): one pull reads one internal batch of the scan (operator counters), rows left in a batch need no pull, a closed stream reads nothing more, a filter's counters chain, and a cursor's answer is unchanged by writes and by checkpoints that free the leaves it has yet to read (file-backed) or by later writes (in memory); a read error after some rows are gathered comes on the next call, then the cursor ends (`query::engine::tests`). DICT lookups are cached for one pull only, and provisional ids keep their values across pulls (`query::engine::ids`). - **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). - **Compatibility and quality**: golden-file corpus of released file formats, cross-platform format compatibility, property-based tests, long-haul smoke coverage, a weekly soak at 10M facts with a 5-hour churn (#392), XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples. diff --git a/src/browser/mod.rs b/src/browser/mod.rs index 4ac1779002..820de7e4f9 100644 --- a/src/browser/mod.rs +++ b/src/browser/mod.rs @@ -299,7 +299,7 @@ impl BrowserDb { DatalogCommand::Retract(_) => bail_coded!(ErrorCode::Api012, "retract"), DatalogCommand::Rule(_) => bail_coded!(ErrorCode::Api012, "rule"), } - let (result, snapshot) = { + let (answer, snapshot) = { let inner = self.inner.borrow(); let snapshot = inner.fact_storage.snapshot()?; let mut executor = DatalogExecutor::new_with_rules_and_functions( @@ -308,9 +308,9 @@ impl BrowserDb { inner.functions.clone(), ); executor.set_snapshot(snapshot.clone()); - (executor.execute(cmd)?, snapshot) + (executor.open(cmd)?, snapshot) }; - crate::Cursor::from_result(result, snapshot) + crate::Cursor::open(answer, snapshot) } /// Apply a batch of pre-materialized facts to the in-memory store and diff --git a/src/cursor.rs b/src/cursor.rs index 9cbc24d904..0ebd8a1860 100644 --- a/src/cursor.rs +++ b/src/cursor.rs @@ -5,17 +5,18 @@ //! is fixed when the cursor opens: writes that commit while it is open do not //! change it. //! -//! The engine behind the cursor currently computes the whole answer when the -//! cursor opens, so `max_results` and `max_derived_facts` apply exactly as they -//! do to [`crate::Minigraf::execute`]. The API is shaped for a streaming engine -//! that produces rows as they are pulled, which is why a cursor is owned (it -//! borrows nothing from the database handle) and why -//! [`Cursor::next_batch`] can fail. +//! Queries the streaming engine runs (#473) produce rows as they are pulled, +//! one internal batch at a time: closing or dropping the cursor stops the +//! work. Other queries compute the whole answer when the cursor opens, so +//! `max_results` and `max_derived_facts` apply exactly as they do to +//! [`crate::Minigraf::execute`]. Either way a cursor is owned (it borrows +//! nothing from the database handle), and [`Cursor::next_batch`] can fail. use crate::error::{ErrorCode, MinigrafError, err_coded}; use crate::graph::storage::Snapshot; use crate::graph::types::Value; -use crate::query::datalog::executor::QueryResult; +use crate::query::datalog::executor::{Answer, QueryResult}; +use crate::query::engine::Stream; /// A forward-only cursor over the rows of one query. /// @@ -42,27 +43,75 @@ use crate::query::datalog::executor::QueryResult; #[derive(Debug)] pub struct Cursor { vars: Vec, + /// Rows ready to return: the whole answer, or the rest of the last batch + /// pulled from `stream`. rows: std::vec::IntoIter>, - /// The state the answer was read from. It pins the committed generation, - /// so no checkpoint reuses its pages while the cursor is open (#543). The - /// answer is computed at open today; a streaming engine (#544) reads it. + /// The engine's operators, while they have rows to give (#544). + stream: Option>, + /// An error met after some rows of a batch were gathered; returned by the + /// next call. + failed: Option, + /// The state the answer is read from. It pins the committed generation, + /// so no checkpoint reuses its pages while the cursor is open (#543). _snapshot: Snapshot, } impl Cursor { - /// Wrap the answer of a query read from `snapshot`. Any other result is a - /// write, which the callers reject before executing. - pub(crate) fn from_result(result: QueryResult, snapshot: Snapshot) -> anyhow::Result { - match result { - QueryResult::QueryResults { vars, results } => Ok(Cursor { - vars, - rows: results.into_iter(), - _snapshot: snapshot, - }), - _ => Err(err_coded!(ErrorCode::Api002)), + /// A cursor over `answer`, read from `snapshot`. A result other than rows + /// is a write, which the callers reject before executing. + pub(crate) fn open(answer: Answer, snapshot: Snapshot) -> anyhow::Result { + let (vars, rows, stream) = match answer { + Answer::Result(QueryResult::QueryResults { vars, results }) => (vars, results, None), + Answer::Result(_) => return Err(err_coded!(ErrorCode::Api002)), + Answer::Stream(stream) => (stream.vars().to_vec(), Vec::new(), Some(stream)), + }; + Ok(Cursor { + vars, + rows: rows.into_iter(), + stream, + failed: None, + _snapshot: snapshot, + }) + } + + /// Pull the next batch of rows from the stream into `rows`. False once + /// the stream has no more. + fn refill(&mut self) -> anyhow::Result { + let Some(stream) = &mut self.stream else { + return Ok(false); + }; + match stream.next_rows() { + Ok(Some(rows)) => { + self.rows = rows.into_iter(); + Ok(true) + } + Ok(None) => { + self.stream = None; + Ok(false) + } + Err(e) => { + self.stream = None; + Err(e) + } } } + /// The engine stream, while it has rows to give. + #[cfg(test)] + pub(crate) fn stream_mut(&mut self) -> Option<&mut Stream> { + self.stream.as_deref_mut() + } + + /// The engine's operator counters (spec §6.3); empty once the stream is + /// done or for an answer computed at open. + #[cfg(test)] + pub(crate) fn counters(&self) -> Vec { + self.stream + .as_ref() + .map(|s| s.counters()) + .unwrap_or_default() + } + /// The variable names of the `:find` clause, in order. Every row has one /// value per variable. pub fn vars(&self) -> &[String] { @@ -74,10 +123,31 @@ impl Cursor { /// /// # Errors /// - /// Reserved for failures while rows are produced. The current engine - /// computes the answer when the cursor opens and never fails here. + /// Returns an error if reading the database fails while rows are + /// produced (an I/O error, or a page that fails its checks). Rows + /// gathered before the failure are returned first, and the error by the + /// next call; after it the cursor returns `None`. pub fn next_batch(&mut self, max_rows: usize) -> Result, MinigrafError> { - let rows: Vec> = self.rows.by_ref().take(max_rows.max(1)).collect(); + if let Some(e) = self.failed.take() { + return Err(e.into()); + } + let max = max_rows.max(1); + let mut rows: Vec> = Vec::new(); + loop { + rows.extend(self.rows.by_ref().take(max - rows.len())); + if rows.len() == max { + break; + } + match self.refill() { + Ok(true) => {} + Ok(false) => break, + Err(e) if rows.is_empty() => return Err(e.into()), + Err(e) => { + self.failed = Some(e); + break; + } + } + } if rows.is_empty() { Ok(None) } else { @@ -85,15 +155,32 @@ impl Cursor { } } - /// Stop reading. Equivalent to dropping the cursor. - pub fn close(self) {} + /// Stop reading: no further rows are read. Equivalent to dropping the + /// cursor. + pub fn close(mut self) { + if let Some(stream) = &mut self.stream { + stream.close(); + } + } } impl Iterator for Cursor { type Item = Result, MinigrafError>; fn next(&mut self) -> Option { - self.rows.next().map(Ok) + if let Some(e) = self.failed.take() { + return Some(Err(e.into())); + } + loop { + if let Some(row) = self.rows.next() { + return Some(Ok(row)); + } + match self.refill() { + Ok(true) => {} + Ok(false) => return None, + Err(e) => return Some(Err(e.into())), + } + } } fn size_hint(&self) -> (usize, Option) { @@ -139,3 +226,156 @@ impl IntoIterator for Batch { self.rows.into_iter() } } + +#[cfg(all(test, not(target_arch = "wasm32")))] +mod tests { + use super::*; + use crate::Minigraf; + use crate::query::engine::{BATCH_ROWS, Counters}; + + const AGES: &str = "(query [:find ?e ?a :where [?e :person/age ?a]])"; + const N: usize = 5000; + + fn people(db: &Minigraf) { + let facts: String = (0..N).map(|i| format!("[:p{i} :person/age {i}]")).collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + } + + fn scan(counters: &[Counters]) -> Counters { + *counters.last().expect("a scan") + } + + /// Every row of `cursor`, `n` at a time. + fn drain(cursor: &mut Cursor, n: usize) -> Vec> { + let mut rows = Vec::new(); + while let Some(batch) = cursor.next_batch(n).unwrap() { + rows.extend(batch.into_rows()); + } + rows + } + + fn sorted(mut rows: Vec>) -> Vec> { + let mut out: Vec> = rows + .drain(..) + .map(|r| { + r.iter() + .flat_map(crate::storage::index::encode_value) + .collect() + }) + .collect(); + out.sort(); + out + } + + /// One pull reads one internal batch; closing reads nothing more. + fn first_batch_then_close(db: &Minigraf) { + let mut cursor = db.query(AGES).unwrap(); + assert_eq!(cursor.next_batch(7).unwrap().expect("a batch").len(), 7); + let counters = cursor.counters(); + let first = scan(&counters); + assert!(first.rows_in > 0, "the scan read keys"); + assert!( + first.rows_in <= 2 * BATCH_ROWS as u64, + "one pull reads one internal batch, not the attribute" + ); + assert_eq!(first.batches, 1); + assert_eq!(counters[0].op, "Project"); + assert_eq!(counters[0].rows_out, first.rows_out); + + // The rest of that batch comes from the cursor's buffer. + let rest = first.rows_out as usize - 7; + assert_eq!( + cursor.next_batch(rest).unwrap().expect("a batch").len(), + rest + ); + assert_eq!(cursor.counters(), counters, "no pull for buffered rows"); + + let mut stream = cursor.stream.take().expect("an engine stream"); + stream.close(); + assert!(stream.next_rows().unwrap().is_none(), "closed"); + assert_eq!(stream.counters(), counters, "no rows read after close"); + } + + #[test] + fn in_memory_cursor_reads_one_batch_at_a_time() { + let db = Minigraf::in_memory().unwrap(); + people(&db); + first_batch_then_close(&db); + } + + #[test] + fn file_cursor_reads_one_batch_at_a_time() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("lazy.graph")).unwrap(); + people(&db); + db.checkpoint().unwrap(); + first_batch_then_close(&db); + } + + #[test] + fn filters_count_their_rows() { + let db = Minigraf::in_memory().unwrap(); + people(&db); + let mut cursor = db + .query("(query [:find ?a :where [?e :person/age ?a] [(< ?a 10)]])") + .unwrap(); + assert_eq!(drain(&mut cursor, 3).len(), 10); + let mut cursor = db + .query("(query [:find ?a :where [?e :person/age ?a] [(< ?a 10)]])") + .unwrap(); + cursor.next_batch(1).unwrap().expect("a batch"); + let counters = cursor.counters(); + let ops: Vec<&str> = counters.iter().map(|c| c.op).collect(); + assert_eq!(ops, ["Project", "Filter", "Scan"]); + assert_eq!(counters[1].rows_in, counters[2].rows_out); + assert_eq!(counters[1].rows_out, counters[0].rows_in); + } + + /// Spec §10: a lazy cursor's answer is unchanged by writes and by + /// checkpoints that free the pages it has yet to read. + #[test] + fn lazy_cursor_keeps_its_answer_across_page_freeing_checkpoints() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("pinned.graph")).unwrap(); + people(&db); + db.checkpoint().unwrap(); + let expected = sorted(drain(&mut db.query(AGES).unwrap(), 1000)); + assert_eq!(expected.len(), N); + + let mut cursor = db.query(AGES).unwrap(); + let mut rows = cursor.next_batch(7).unwrap().expect("a batch").into_rows(); + assert!( + scan(&cursor.counters()).rows_in < N as u64, + "the cursor has keys left to read" + ); + // Rewrite every leaf of the attribute, several times over. + for round in 0..4 { + let facts: String = (0..N) + .map(|i| format!("[:p{i} :person/age {}]", i + (round + 1) * N)) + .collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + db.checkpoint().unwrap(); + } + db.execute("(transact [[:late :person/age -1]])").unwrap(); + assert!( + db.verify().unwrap().is_ok(), + "verify clean with the cursor open" + ); + rows.extend(drain(&mut cursor, 500)); + assert_eq!(sorted(rows), expected, "the answer at open"); + } + + #[test] + fn in_memory_lazy_cursor_ignores_later_writes() { + let db = Minigraf::in_memory().unwrap(); + people(&db); + let expected = sorted(drain(&mut db.query(AGES).unwrap(), 1000)); + let mut cursor = db.query(AGES).unwrap(); + let mut rows = cursor.next_batch(7).unwrap().expect("a batch").into_rows(); + db.execute("(retract [[:p0 :person/age 0] [:p4999 :person/age 4999]])") + .unwrap(); + db.execute("(transact [[:late :person/age -1]])").unwrap(); + rows.extend(cursor.by_ref().map(Result::unwrap)); + assert_eq!(sorted(rows), expected, "the answer at open"); + } +} diff --git a/src/db.rs b/src/db.rs index 674a7a782a..bc13a0b292 100644 --- a/src/db.rs +++ b/src/db.rs @@ -798,9 +798,10 @@ impl Minigraf { /// /// The cursor's answer is fixed when this returns: writes that commit /// while it is open do not change it. The cursor owns what it needs, so it - /// can outlive this handle and move to another thread. While the engine - /// computes the whole answer up front, `max_results` and - /// `max_derived_facts` apply exactly as they do to [`Minigraf::execute`]. + /// can outlive this handle and move to another thread. Queries the + /// streaming engine runs produce rows as they are pulled; others compute + /// the whole answer here, and `max_results` and `max_derived_facts` apply + /// exactly as they do to [`Minigraf::execute`]. /// /// # Errors /// @@ -828,8 +829,8 @@ impl Minigraf { DatalogCommand::Rule(_) => bail_coded!(ErrorCode::Api012, "rule"), } let snapshot = self.inner.fact_storage.snapshot()?; - let result = self.read_executor(snapshot.clone()).execute(cmd)?; - Cursor::from_result(result, snapshot) + let answer = self.read_executor(snapshot.clone()).open(cmd)?; + Cursor::open(answer, snapshot) } /// Stream every fact record (assertions and retractions, with their diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 98b2296460..90b663c6dd 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -92,6 +92,13 @@ fn collect_all_patterns(clauses: &[WhereClause]) -> Vec { patterns } +/// What [`DatalogExecutor::open`] gives a cursor: a whole result, or a +/// query on the streaming engine to pull rows from. +pub(crate) enum Answer { + Result(QueryResult), + Stream(Box), +} + /// The result of executing a Datalog command via [`crate::db::Minigraf::execute`]. /// /// Pattern-match on this to distinguish query results from write confirmations: @@ -521,6 +528,22 @@ impl DatalogExecutor { /// Execute a query: find matching facts and return specified variables fn execute_query(&self, query: DatalogQuery) -> Result { + match self.open_query(query)? { + Answer::Result(result) => Ok(result), + Answer::Stream(stream) => stream.collect(), + } + } + + /// Run `command` for a cursor: a query the streaming engine runs is + /// opened, not run; anything else runs as [`Self::execute`] runs it. + pub(crate) fn open(&self, command: DatalogCommand) -> Result { + match command { + DatalogCommand::Query(query) => self.open_query(query), + command => self.execute(command).map(Answer::Result), + } + } + + fn open_query(&self, query: DatalogQuery) -> Result { // Resolve :find functions up front so an unknown name fails whether or // not any row matches (#414). { @@ -534,7 +557,7 @@ impl DatalogExecutor { // Check if query uses rules if query.uses_rules() { // Use StratifiedEvaluator for queries with rule invocations (handles negation and strata) - return self.execute_query_with_rules(query); + return self.execute_query_with_rules(query).map(Answer::Result); } // Warn about queries with no binding mechanism @@ -547,24 +570,34 @@ impl DatalogExecutor { if self.facts_override.is_none() && let Some(plan) = crate::query::engine::plan(&query) { - let registry = self - .functions - .read() - .map_err(|_| err_coded!(ErrorCode::Qry008))?; - check_clauses(&query, ®istry)?; + { + let registry = self + .functions + .read() + .map_err(|_| err_coded!(ErrorCode::Qry008))?; + check_clauses(&query, ®istry)?; + } let snapshot = self.read_snapshot()?; - let result = crate::query::engine::run(&snapshot, plan, ®istry); - drop(registry); - if let Some(result) = result { + if let Some(stream) = + crate::query::engine::open(snapshot.clone(), plan, self.functions.clone()) + { + #[cfg(test)] + crate::query::engine::RUNS.with(|r| r.set(r.get() + 1)); + // The comparison drains a second stream, so the one returned + // stays unread. #[cfg(any(test, feature = "test-oracle"))] - crate::query::engine::oracle::check( - &result, - &self.oracle(snapshot).execute_query_on_executor(query), - ); - return result; + if let Some(again) = crate::query::engine::plan(&query).and_then(|plan| { + crate::query::engine::open(snapshot.clone(), plan, self.functions.clone()) + }) { + crate::query::engine::oracle::check( + &again.collect(), + &self.oracle(snapshot).execute_query_on_executor(query), + ); + } + return Ok(Answer::Stream(Box::new(stream))); } } - self.execute_query_on_executor(query) + self.execute_query_on_executor(query).map(Answer::Result) } /// This executor over `snapshot`, for the engine's oracle (#473 spec §9). diff --git a/src/query/datalog/prepared.rs b/src/query/datalog/prepared.rs index 4e595b3831..802a4ef5d8 100644 --- a/src/query/datalog/prepared.rs +++ b/src/query/datalog/prepared.rs @@ -118,8 +118,8 @@ impl PreparedQuery { pub fn query(&self, bindings: &[(&str, BindValue)]) -> Result { let run = || { let snapshot = self.fact_storage.snapshot()?; - let result = self.execute_inner(bindings, snapshot.clone())?; - Cursor::from_result(result, snapshot) + let (executor, command) = self.bind(bindings, snapshot.clone())?; + Cursor::open(executor.open(command)?, snapshot) }; run().map_err(MinigrafError::from) } @@ -130,6 +130,16 @@ impl PreparedQuery { bindings: &[(&str, BindValue)], snapshot: Snapshot, ) -> Result { + let (executor, command) = self.bind(bindings, snapshot)?; + executor.execute(command) + } + + /// The query with `bindings`, and an executor reading from `snapshot`. + fn bind( + &self, + bindings: &[(&str, BindValue)], + snapshot: Snapshot, + ) -> Result<(DatalogExecutor, DatalogCommand)> { let binding_map: HashMap<&str, &BindValue> = bindings.iter().map(|(name, val)| (*name, val)).collect(); @@ -147,7 +157,7 @@ impl PreparedQuery { self.functions.clone(), ); executor.set_snapshot(snapshot); - executor.execute(DatalogCommand::Query(filled_query)) + Ok((executor, DatalogCommand::Query(filled_query))) } } diff --git a/src/query/engine/filter.rs b/src/query/engine/filter.rs index 1359825a30..fba53be89f 100644 --- a/src/query/engine/filter.rs +++ b/src/query/engine/filter.rs @@ -4,18 +4,63 @@ //! An expression sees only the variables it reads, turned into values for //! the row; a binding expression's result becomes a cell again. -use super::Ctx; use super::batch::Batch; use super::cell::{Cell, Scalar}; use super::plan::{Step, Term, Vars}; use super::project::value; +use super::{Counters, Ctx, Operator}; use crate::query::datalog::executor::{eval_expr, is_truthy}; use crate::query::datalog::types::Expr; use anyhow::Result; use std::collections::HashMap; +/// One clause after the scan, over the batches of its child. +pub(crate) struct Apply { + child: Box, + step: Step, + counters: Counters, +} + +impl Apply { + pub(crate) fn new(child: Box, step: Step) -> Self { + let op = match step { + Step::Pseudo { .. } => "Pseudo", + Step::Filter(..) => "Filter", + Step::Bind(..) => "Bind", + }; + Apply { + child, + step, + counters: Counters::new(op), + } + } +} + +impl Operator for Apply { + fn next_batch(&mut self, ctx: &mut Ctx<'_>) -> Result> { + while let Some(batch) = self.child.next_batch(ctx)? { + self.counters.rows_in += batch.len as u64; + let batch = apply(&self.step, batch, ctx)?; + if batch.len > 0 { + self.counters.out(&batch); + return Ok(Some(batch)); + } + } + Ok(None) + } + + fn close(&mut self) { + self.child.close(); + } + + fn counters(&self, out: &mut Vec) { + out.push(self.counters); + self.child.counters(out); + } +} + /// Apply `step` to `batch`. -pub(crate) fn apply(step: &Step, mut batch: Batch, ctx: &mut Ctx<'_>) -> Result { +fn apply(step: &Step, mut batch: Batch, ctx: &mut Ctx<'_>) -> Result { match step { Step::Pseudo { col, value } => { let meta = batch.cols.get(*col).cloned().unwrap_or_default(); @@ -51,7 +96,7 @@ pub(crate) fn apply(step: &Step, mut batch: Batch, ctx: &mut Ctx<'_>) -> Result< for i in 0..batch.len { match eval(expr, vars, &batch, i, ctx)? { Some(v) => { - out.push(Cell::of_value(&mut ctx.ids, ctx.keys, &v)?); + out.push(Cell::of_value(ctx.ids, ctx.keys, &v)?); keep.push(true); } None => keep.push(false), diff --git a/src/query/engine/ids.rs b/src/query/engine/ids.rs index 6885e0f120..95874ea993 100644 --- a/src/query/engine/ids.rs +++ b/src/query/engine/ids.rs @@ -4,6 +4,11 @@ //! strings; those the DICT lacks get provisional ids, from the generation's //! `next_eid` / `next_iid` upwards, the first time the query meets them. //! Provisional ids are never written anywhere. +//! +//! Provisional ids are kept for the whole query, so that each pending UUID +//! or ident keeps its id. DICT lookups are only cached until the next pull +//! ([`IdSpace::end_pull`]): a DICT id never changes, and a cache that grew +//! with every row a cursor returns would hold the whole answer. use crate::error::{ErrorCode, err_coded}; use crate::graph::types::EntityId; @@ -18,6 +23,14 @@ pub(crate) struct IdSpace { dict_iids: u64, next_eid: u64, next_iid: u64, + /// Provisional ids, for the whole query. + provisional: Maps, + /// DICT lookups, until the next pull. + dict: Maps, +} + +#[derive(Default)] +struct Maps { eid_by_uuid: HashMap, uuid_by_eid: HashMap, iid_by_name: HashMap, u64>, @@ -35,53 +48,78 @@ impl IdSpace { dict_iids: iids, next_eid: eids, next_iid: iids, - eid_by_uuid: HashMap::new(), - uuid_by_eid: HashMap::new(), - iid_by_name: HashMap::new(), - name_by_iid: HashMap::new(), + provisional: Maps::default(), + dict: Maps::default(), + } + } + + /// Forget the DICT lookups of the last pull. + pub(crate) fn end_pull(&mut self) { + self.dict = Maps::default(); + } + + /// DICT lookups cached now. + #[cfg(test)] + pub(crate) fn dict_cached(&self) -> usize { + self.dict.uuid_by_eid.len() + self.dict.name_by_iid.len() + } + + /// The maps that hold `eid` or `iid`. + fn maps(&mut self, provisional: bool) -> &mut Maps { + if provisional { + &mut self.provisional + } else { + &mut self.dict } } /// The id of `uuid`: its DICT id, or a provisional one. pub(crate) fn eid(&mut self, keys: Option<&dyn KeySource>, uuid: &EntityId) -> Result { - if let Some(&e) = self.eid_by_uuid.get(uuid) { - return Ok(e); + for maps in [&self.provisional, &self.dict] { + if let Some(&e) = maps.eid_by_uuid.get(uuid) { + return Ok(e); + } } - let e = match keys.map(|k| k.eid_of(uuid)).transpose()?.flatten() { - Some(e) => e, + let (e, provisional) = match keys.map(|k| k.eid_of(uuid)).transpose()?.flatten() { + Some(e) => (e, false), None => { let e = self.next_eid; self.next_eid += 1; - e + (e, true) } }; - self.eid_by_uuid.insert(*uuid, e); - self.uuid_by_eid.insert(e, *uuid); + let maps = self.maps(provisional); + maps.eid_by_uuid.insert(*uuid, e); + maps.uuid_by_eid.insert(e, *uuid); Ok(e) } /// The id of the ident `name`: its DICT id, or a provisional one. pub(crate) fn iid(&mut self, keys: Option<&dyn KeySource>, name: &str) -> Result { - if let Some(&i) = self.iid_by_name.get(name) { - return Ok(i); + for maps in [&self.provisional, &self.dict] { + if let Some(&i) = maps.iid_by_name.get(name) { + return Ok(i); + } } - let i = match keys.map(|k| k.iid_of(name)).transpose()?.flatten() { - Some(i) => u64::from(i), + let (i, provisional) = match keys.map(|k| k.iid_of(name)).transpose()?.flatten() { + Some(i) => (u64::from(i), false), None => { let i = self.next_iid; self.next_iid += 1; - i + (i, true) } }; let name: Arc = Arc::from(name); - self.iid_by_name.insert(name.clone(), i); - self.name_by_iid.insert(i, name); + let maps = self.maps(provisional); + maps.iid_by_name.insert(name.clone(), i); + maps.name_by_iid.insert(i, name); Ok(i) } /// The entity with id `eid`. pub(crate) fn uuid(&mut self, keys: Option<&dyn KeySource>, eid: u64) -> Result { - if let Some(u) = self.uuid_by_eid.get(&eid) { + let maps = self.maps(eid >= self.dict_eids); + if let Some(u) = maps.uuid_by_eid.get(&eid) { return Ok(*u); } let Some(k) = keys.filter(|_| eid < self.dict_eids) else { @@ -91,14 +129,15 @@ impl IdSpace { )); }; let u = k.uuid_of(eid)?; - self.uuid_by_eid.insert(eid, u); - self.eid_by_uuid.insert(u, eid); + self.dict.uuid_by_eid.insert(eid, u); + self.dict.eid_by_uuid.insert(u, eid); Ok(u) } /// The ident with id `iid`. pub(crate) fn name(&mut self, keys: Option<&dyn KeySource>, iid: u64) -> Result> { - if let Some(n) = self.name_by_iid.get(&iid) { + let maps = self.maps(iid >= self.dict_iids); + if let Some(n) = maps.name_by_iid.get(&iid) { return Ok(n.clone()); } let k = keys.filter(|_| iid < self.dict_iids); @@ -109,8 +148,28 @@ impl IdSpace { )); }; let n: Arc = Arc::from(k.ident_of(i)?); - self.name_by_iid.insert(iid, n.clone()); - self.iid_by_name.insert(n.clone(), iid); + self.dict.name_by_iid.insert(iid, n.clone()); + self.dict.iid_by_name.insert(n.clone(), iid); Ok(n) } } + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn provisional_ids_outlive_a_pull() { + let mut ids = IdSpace::new(None); + let (a, b) = (uuid::Uuid::from_u128(1), uuid::Uuid::from_u128(2)); + let ea = ids.eid(None, &a).unwrap(); + let ia = ids.iid(None, ":a").unwrap(); + ids.end_pull(); + assert_eq!(ids.eid(None, &a).unwrap(), ea); + assert_ne!(ids.eid(None, &b).unwrap(), ea); + assert_eq!(ids.iid(None, ":a").unwrap(), ia); + assert!(ids.uuid(None, ea).unwrap() == a, "round trip"); + assert_eq!(&*ids.name(None, ia).unwrap(), ":a"); + assert!(ids.uuid(None, 99).is_err(), "unknown id"); + } +} diff --git a/src/query/engine/mod.rs b/src/query/engine/mod.rs index e45a33944b..e3684641ec 100644 --- a/src/query/engine/mod.rs +++ b/src/query/engine/mod.rs @@ -18,13 +18,17 @@ mod scan; #[cfg(all(test, not(target_arch = "wasm32")))] mod tests; +use crate::error::{ErrorCode, err_coded}; use crate::graph::storage::Snapshot; +use crate::graph::types::Value; use crate::query::datalog::executor::QueryResult; use crate::query::datalog::functions::FunctionRegistry; -use crate::storage::KeySource; +use crate::storage::{CommittedReader, KeySource}; use anyhow::Result; +use batch::Batch; use ids::IdSpace; pub(crate) use plan::{Plan, plan}; +use std::sync::{Arc, RwLock}; #[cfg(test)] thread_local! { @@ -35,61 +39,201 @@ thread_local! { /// Most rows in one internal batch (spec §5.1). pub(crate) const BATCH_ROWS: usize = 1024; -/// What every operator of one query reads and shares. +/// What every operator of one query reads and shares, for one pull. pub(crate) struct Ctx<'a> { snapshot: &'a Snapshot, /// Key-level reads of the committed generation; `None` for an in-memory /// database. keys: Option<&'a dyn KeySource>, - ids: IdSpace, + ids: &'a mut IdSpace, /// Predicates for expression clauses. functions: &'a FunctionRegistry, } -/// Run `plan` over `snapshot`, or `None` when the snapshot's committed +/// What one operator has done (spec §6.3): rows it read or received, rows +/// and batches it passed on. +#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)] +pub(crate) struct Counters { + pub(crate) op: &'static str, + pub(crate) rows_in: u64, + pub(crate) rows_out: u64, + pub(crate) batches: u64, +} + +impl Counters { + fn new(op: &'static str) -> Self { + Counters { + op, + ..Counters::default() + } + } + + /// Count `batch` as passed on. + fn out(&mut self, batch: &Batch) { + self.rows_out += batch.len as u64; + self.batches += 1; + } +} + +/// One operator of a query (spec §6). `next_batch` never returns an empty +/// batch; after `close`, it returns `None` and reads nothing. +pub(crate) trait Operator: Send { + fn next_batch(&mut self, ctx: &mut Ctx<'_>) -> Result>; + /// Stop: release what the operator holds and close its children. + fn close(&mut self); + /// This operator's counters, then its children's. + fn counters(&self, out: &mut Vec); +} + +/// A query on the engine: its operator tree over one snapshot, pulled one +/// batch at a time. Owned, so a cursor can hold it. +pub(crate) struct Stream { + snapshot: Snapshot, + ids: IdSpace, + /// Read-locked for each pull. Predicates are never replaced once + /// registered (`INT-040`), so the answer does not change between pulls. + functions: Arc>, + root: Box, + /// The slot of each `:find` variable. + find: Vec, + vars: Vec, + project: Counters, + closed: bool, +} + +impl std::fmt::Debug for Stream { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + f.debug_struct("Stream") + .field("vars", &self.vars) + .field("closed", &self.closed) + .field("counters", &self.counters()) + .finish_non_exhaustive() + } +} + +/// Open `plan` over `snapshot`, or `None` when the snapshot's committed /// reader has no keys (a test reader) and the executor must run it. -pub(crate) fn run( - snapshot: &Snapshot, +pub(crate) fn open( + snapshot: Snapshot, plan: Plan, - functions: &FunctionRegistry, -) -> Option> { + functions: Arc>, +) -> Option { let keys = match &snapshot.committed { Some(reader) => Some(reader.key_source()?), None => None, }; - #[cfg(test)] - RUNS.with(|r| r.set(r.get() + 1)); - Some(execute(snapshot, keys, plan, functions)) -} - -fn execute( - snapshot: &Snapshot, - keys: Option<&dyn KeySource>, - plan: Plan, - functions: &FunctionRegistry, -) -> Result { + let ids = IdSpace::new(keys); let Plan { scan, steps, find, vars, } = plan; - let mut results = Vec::new(); - let mut ctx = Ctx { + let mut root: Box = Box::new(scan::Scan::new(scan)); + for step in steps { + root = Box::new(filter::Apply::new(root, step)); + } + Some(Stream { snapshot, - keys, - ids: IdSpace::new(keys), + ids, functions, - }; - let mut scan = scan::Scan::new(scan); - while let Some(mut batch) = scan.next_batch(&mut ctx)? { - for step in &steps { - if batch.len == 0 { - break; - } - batch = filter::apply(step, batch, &mut ctx)?; + root, + find, + vars, + project: Counters::new("Project"), + closed: false, + }) +} + +impl Stream { + /// A stream of `root`'s batches, projecting slot 0 as `?x`. + #[cfg(test)] + pub(crate) fn for_test(snapshot: Snapshot, root: Box) -> Self { + Stream { + snapshot, + ids: IdSpace::new(None), + functions: Arc::new(RwLock::new(FunctionRegistry::with_builtins())), + root, + find: vec![0], + vars: vec!["?x".to_string()], + project: Counters::new("Project"), + closed: false, + } + } + + /// The rows of the next batch, as values, or `None` once every row has + /// been returned. Never an empty batch. After an error, or `close`, it + /// returns `None`. + pub(crate) fn next_rows(&mut self) -> Result>>> { + if self.closed { + return Ok(None); + } + let rows = self.pull(); + self.ids.end_pull(); + if !matches!(rows, Ok(Some(_))) { + self.close(); } - results.extend(project::project(&batch, &find, &mut ctx)?); + rows + } + + fn pull(&mut self) -> Result>>> { + let functions = self + .functions + .read() + .map_err(|_| err_coded!(ErrorCode::Qry008))?; + let mut ctx = Ctx { + snapshot: &self.snapshot, + keys: self + .snapshot + .committed + .as_deref() + .and_then(CommittedReader::key_source), + ids: &mut self.ids, + functions: &functions, + }; + let Some(batch) = self.root.next_batch(&mut ctx)? else { + return Ok(None); + }; + self.project.rows_in += batch.len as u64; + let rows = project::project(&batch, &self.find, &mut ctx)?; + self.project.out(&batch); + Ok(Some(rows)) + } + + /// Stop every operator. Idempotent; dropping the stream does the same. + pub(crate) fn close(&mut self) { + if !self.closed { + self.closed = true; + self.root.close(); + } + } + + pub(crate) fn vars(&self) -> &[String] { + &self.vars + } + + /// The counters of every operator, from `Project` down to the scan. + pub(crate) fn counters(&self) -> Vec { + let mut out = vec![self.project]; + self.root.counters(&mut out); + out + } + + /// Every row, as one result. + pub(crate) fn collect(mut self) -> Result { + let mut results = Vec::new(); + while let Some(rows) = self.next_rows()? { + results.extend(rows); + } + Ok(QueryResult::QueryResults { + vars: std::mem::take(&mut self.vars), + results, + }) + } +} + +impl Drop for Stream { + fn drop(&mut self) { + self.close(); } - Ok(QueryResult::QueryResults { vars, results }) } diff --git a/src/query/engine/scan.rs b/src/query/engine/scan.rs index 7460d818d7..17d3266631 100644 --- a/src/query/engine/scan.rs +++ b/src/query/engine/scan.rs @@ -9,7 +9,7 @@ use super::batch::Batch; use super::cell::{Cell, Scalar}; use super::plan::{Meta, ScanSpec, Term, Valid, ValueConst, names}; -use super::{BATCH_ROWS, Ctx}; +use super::{BATCH_ROWS, Counters, Ctx, Operator}; use crate::graph::storage::PendingResume; use crate::graph::types::{EntityId, Fact, Value}; use crate::storage::keys::{self, Index, KeyFact, KeyValue, SHORT_STRING_MAX, ValueKind}; @@ -22,6 +22,8 @@ pub(crate) struct Scan { state: State, keys_buf: Vec, facts_buf: Vec, + /// `rows_in` counts the live keys and pending facts read. + counters: Counters, } enum State { @@ -82,10 +84,13 @@ impl Scan { state: State::Start, keys_buf: Vec::new(), facts_buf: Vec::new(), + counters: Counters::new("Scan"), } } +} - pub(crate) fn next_batch(&mut self, ctx: &mut Ctx<'_>) -> Result> { +impl Operator for Scan { + fn next_batch(&mut self, ctx: &mut Ctx<'_>) -> Result> { loop { let mut batch = Batch::new(self.spec.width); match &mut self.state { @@ -111,6 +116,7 @@ impl Scan { if c.resume.is_none() { c.next += 1; } + self.counters.rows_in += self.keys_buf.len() as u64; let valid = valid_at(self.spec.valid, ctx); let mut row = vec![None; self.spec.width]; for kf in &self.keys_buf { @@ -154,6 +160,7 @@ impl Scan { BATCH_ROWS, &mut self.facts_buf, )?; + self.counters.rows_in += self.facts_buf.len() as u64; let valid = valid_at(self.spec.valid, ctx); let mut row = vec![None; self.spec.width]; for f in &self.facts_buf { @@ -163,7 +170,7 @@ impl Scan { continue; } let keys = ctx.keys; - let ids = &mut ctx.ids; + let ids = &mut *ctx.ids; if fill(&self.spec.e, &mut row, || { Ok(Cell::Eid(ids.eid(keys, &f.entity)?)) })? && fill(&self.spec.a, &mut row, || { @@ -191,10 +198,21 @@ impl Scan { State::Done => return Ok(None), } if batch.len > 0 { + self.counters.out(&batch); return Ok(Some(batch)); } } } + + fn close(&mut self) { + self.state = State::Done; + self.keys_buf = Vec::new(); + self.facts_buf = Vec::new(); + } + + fn counters(&self, out: &mut Vec) { + out.push(self.counters); + } } fn set(row: &mut [Option], slot: usize, n: i64) { diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 6ac4bd6031..650203c2d2 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -457,3 +457,104 @@ fn cross_kind_constants_read_their_avet_ranges() { drop(file); check(&Minigraf::open(&path).unwrap()); } + +/// Gives `rows` integers in one batch, then fails. +struct FailAfter { + rows: i64, + sent: bool, + closed: bool, +} + +impl super::Operator for FailAfter { + fn next_batch(&mut self, _: &mut super::Ctx<'_>) -> anyhow::Result> { + assert!(!self.closed, "no pull after close"); + if self.sent { + anyhow::bail!("read failed"); + } + self.sent = true; + let mut batch = super::Batch::new(1); + for n in 0..self.rows { + batch.push(&mut [Some(super::cell::Cell::Val(super::cell::Scalar::Int(n)))]); + } + Ok(Some(batch)) + } + + fn close(&mut self) { + self.closed = true; + } + + fn counters(&self, _: &mut Vec) {} +} + +fn failing_cursor(rows: i64) -> crate::Cursor { + let snapshot = crate::graph::storage::FactStorage::new() + .snapshot() + .unwrap(); + let stream = super::Stream::for_test( + snapshot.clone(), + Box::new(FailAfter { + rows, + sent: false, + closed: false, + }), + ); + crate::Cursor::open( + crate::query::datalog::executor::Answer::Stream(Box::new(stream)), + snapshot, + ) + .unwrap() +} + +#[test] +fn cursor_returns_gathered_rows_before_a_read_error() { + let mut cursor = failing_cursor(3); + assert_eq!(cursor.next_batch(10).unwrap().expect("rows first").len(), 3); + assert!(cursor.next_batch(10).is_err(), "then the error"); + assert!(cursor.next_batch(10).unwrap().is_none(), "then done"); + + let mut cursor = failing_cursor(3); + assert_eq!(cursor.next_batch(3).unwrap().expect("rows").len(), 3); + assert!( + cursor.next_batch(3).is_err(), + "an error with no rows gathered" + ); + assert!(cursor.next_batch(3).unwrap().is_none()); + + let items: Vec = failing_cursor(2).map(|r| r.is_ok()).collect(); + assert_eq!( + items, + [true, true, false], + "the iterator ends after the error" + ); + + let mut cursor = failing_cursor(2); + assert_eq!(cursor.next_batch(5).unwrap().expect("rows").len(), 2); + assert!(cursor.next().expect("the error").is_err()); + assert!(cursor.next().is_none()); +} + +/// DICT lookups are cached for one pull only, so a cursor's memory does not +/// grow with the rows it returns; pending entities keep their ids. +#[test] +fn dict_cache_is_dropped_after_each_pull() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("ids.graph")).unwrap(); + let facts: String = (0..3000) + .map(|i| format!("[:p{i} :person/age {i}]")) + .collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + db.checkpoint().unwrap(); + db.execute("(transact [[:new :person/age 1] [:new :person/age 2]])") + .unwrap(); + let mut cursor = db + .query("(query [:find ?e ?a :where [?e :person/age ?a]])") + .unwrap(); + let mut rows = 0; + while let Some(batch) = cursor.next_batch(500).unwrap() { + rows += batch.len(); + if let Some(stream) = cursor.stream_mut() { + assert_eq!(stream.ids.dict_cached(), 0, "no DICT lookups kept"); + } + } + assert_eq!(rows, 3002); +}