diff --git a/CHANGELOG.md b/CHANGELOG.md index 48e10d8634..f9a04c86f4 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -46,6 +46,7 @@ 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). - **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. @@ -55,6 +56,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Fixed +- **Prepared queries use the database's rule limit** (#549). `PreparedQuery::execute` and `query` ran a rule query with the default `max_derived_facts` of 1,000,000 whatever `OpenOptions` set; they now use the database's limit, as `execute` does, and its `query_memory_limit`. - **An `or` branch in a rule body knows the registered predicates** (#548). A rule with `or`/`or-join` evaluated its branches with the built-in functions only, so a predicate registered with `register_predicate` in a branch (`(or [(big? ?v)] [?x :special true])`) was unknown there. Branches now get the database's functions, as the rest of the rule body does. - **A pseudo-attribute in a rule body reads the stored fact** (#661). In a rule without `not`, `not-join`, `or` or `or-join`, `:db/valid-from`, `:db/valid-to`, `:db/tx-count` and `:db/tx-id` read the rule evaluator's working copy of the fact: valid-from was the time the query ran, valid-to forever, and the tx-count and tx-id those of the copy. With `[:a :edge :b]` valid from 2020-01-01 to 2021-01-01, `(rule [(vf ?x ?t) [?x :edge ?y] [?x :db/valid-from ?t]])` returned the query's time for `:a`; it now returns 2020-01-01, as the same pattern in a query body does. Stored data was never affected. Present since v0.15.0; fixed on v2.x too. - **Rule queries with a literal argument return every row** (#608). Magic-sets rewriting restricts a rule to the facts its callers demand, but it took each rule's bound arguments from the first call it saw and assumed every other call matched. A call that did not — the same rule called with free arguments elsewhere in the query, a call inside `or` or `not`, a call from a rule the query calls with free arguments, or a rule-body call whose argument nothing bound yet — either failed with `INT-022` (`(chain ?x :c)` with `(chain ?x ?y) :- (link ?x ?m) (chain ?m ?y)`) or silently returned too few rows (`(link ?x :c) (link ?p ?q)` returned only the `:c` edges for `?p ?q`). A query with both arguments literal next to another rule call also lost its rows. The demand on each rule is now the one every call site supplies, and a rule some call site reads in full is evaluated in full. Present since v1.2.0. @@ -99,6 +101,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **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`). - **`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. - **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 eb7cc62ebe..d64892777c 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -141,13 +141,13 @@ 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: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a rule query whose every evaluated rule body plans), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, `HashJoin` otherwise; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `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`/`rewind`/`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. +3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a rule query whose every evaluated rule body plans), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, `HashJoin` otherwise; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `meter.rs` (#549: one `Meter` per query, shared by every holder of state through a `Held` — hash join build sides, `not`/`or` tables, distinct sets, aggregate groups, window rows, rule relations and their temporaries, `IdSpace`; each entry charged by a per-entry estimate before it is inserted, containers grown with `try_reserve`, released on `rewind`/`close`/drop; over `OpenOptions::query_memory_limit`, or a refused allocation, is `QRY-012`; `Stream::close` drops the operator tree, keeping its counters), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree; an engine `QRY-012` agrees with any answer). `mod.rs`: `Operator` (`next_batch`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` 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`) +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) - `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) @@ -206,7 +206,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1702 tests** (1691 passing, 11 ignored; unit + integration + doc). +**1720 tests** (1709 passing, 11 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 735c85ef78..6a93bc28fb 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 1702 tests +cargo test # run 1720 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index f9bc8bc610..8bd05bbadd 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -146,6 +146,7 @@ with no `CodedError` anywhere in its chain. | QRY-009 | Rules lock poisoned | Query Execution | | QRY-010 | Unknown aggregate function | Query Execution | | QRY-011 | Unknown window function | Query Execution | +| QRY-012 | Query memory limit exceeded | Query Execution | | QRY-013 | Rule head entity is not an entity | Query Execution | | STG-001 | Invalid header: too short | Storage | | STG-002 | Invalid magic number: not a .graph file | Storage | @@ -2306,11 +2307,35 @@ predicate evaluation, or fact transacting. ``` *`frob` is not a window built-in; register it first* +### QRY-012 Query memory limit exceeded + +**Error text**: `query memory limit exceeded: {}` + +The text after the colon takes one of two forms: +- `{op} needs {n} more bytes and the query already holds {used} of its {limit}-byte limit` +- `the allocator refused {n} bytes for {op}` + +**Cause**: A query held more state than `OpenOptions::query_memory_limit` allows, or the allocator refused memory one of its operators asked for. `{op}` names the operator that would have held the bytes: `HashJoin`, `AntiJoin`, `Union`, `Distinct`, `Aggregate`, `Window`, `Relations` or `Recursive` (a rule query's derived facts), or `IdSpace` (the query's entity and ident ids). Each operator counts an estimate of what it holds, per entry, so the count is the same on every platform. The limit is off by default (`usize::MAX`), so the first form only comes when a limit is set. The second form can come without one: it replaces the abort the process would otherwise suffer. A query inside a write transaction that has staged writes is not counted yet. + +After the error the query's state is freed. The database, other queries and other cursors are unaffected. Through a cursor, the rows already returned stay returned and the error comes on the next call. A rule query can fail when it is opened, while its rules are evaluated. + +**Resolution**: +- Raise `OpenOptions::query_memory_limit`, or leave it at the default. +- Narrow the query: bind a constant, add a join variable between patterns that share none (a cartesian product holds one side in full), or group by fewer variables. +- Read a large answer through `Minigraf::query` instead of `execute`, which holds every row. + +**Example**: +```rust +let db = Minigraf::open_with_options("app.graph", OpenOptions::new().query_memory_limit(64))?; +db.execute("(query [:find ?g (count ?e) :where [?e :g ?g]])")?; +``` +*`Aggregate` needs more than 64 bytes for its first group* + ### QRY-013 Rule head entity is not an entity **Error text**: `rule head entity is not an entity: rule '{}' gives a {} where a ref or a keyword is needed` -**Cause**: A rule produced a head whose first argument, the entity of the fact it derives, is not an entity: a string, a number, a boolean or `nil`. Only a ref, or a keyword (which names the entity `uuidv5(keyword)`), is an entity. The head's second argument, the value, may be any value. The query that invoked the rule fails, whether the rule has `not`/`not-join`/`or`/`or-join` clauses or not. Before v3.0.0 a positive rule failed with INT-022 and a rule with `not`/`or` clauses silently dropped the row. (QRY-012 is reserved.) +**Cause**: A rule produced a head whose first argument, the entity of the fact it derives, is not an entity: a string, a number, a boolean or `nil`. Only a ref, or a keyword (which names the entity `uuidv5(keyword)`), is an entity. The head's second argument, the value, may be any value. The query that invoked the rule fails, whether the rule has `not`/`not-join`/`or`/`or-join` clauses or not. Before v3.0.0 a positive rule failed with INT-022 and a rule with `not`/`or` clauses silently dropped the row. **Resolution**: - Put an entity variable first in the head: `(owner ?item ?person)`, not `(owner ?name ?item)` where `?name` binds a string. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index f98ff83fab..20188b7a9f 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-21 with `cargo test --quiet` -**Result**: 1,691 passing tests and 11 ignored tests (1,702 total) +**Result**: 1,709 passing tests and 11 ignored tests (1,720 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). @@ -19,6 +19,7 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **`or` with no shared variable** (#610): `tests/disjunction_test.rs` checks that an `or` sharing no variable with the earlier clauses joins as a cross product, before or after them, through the seeded path (a branch with `not`) and in a rule body, keeps the earlier clauses' variables and fact metadata (a pseudo-attribute), and gives no rows when no branch matches. - **Prepared time travel** (#603): `tests/prepared_statements_test.rs` runs literal `:as-of` (counter and timestamp), `:valid-at`, `:any-valid-time` and a per-fact pseudo-attribute query through `execute`, a prepared `execute` and a prepared cursor, which must agree; a `prepared.rs` unit test checks that `substitute` keeps non-slot `:as-of` and `:valid-at`. - **Rule queries on the engine** (`tests/recursive_engine_test.rs`, 10 tests; #548): linear and non-linear transitive closure, mutual recursion, strata whose `not` and `or` rules recurse (#633's cases), naive rules (a same-stratum read in an `or` branch, through a `:p` pattern, through `[?y ?a ?z]`), derived facts visible to every pattern and the magic-set predicate's attribute, identity of derived facts (keyword vs ref, `-0.0` vs `0.0`, long strings, a head equal to a stored fact), `nil` metadata and `:db/valid-at` over derived facts, one-argument heads, `QRY-013` and `INT-022` heads, both `INT-020` limits, and rule queries with aggregates, expressions, `not-join`, `or` and windows; each in memory, on a file with pending facts and after a checkpoint, and under `test-oracle` against the executor. Engine unit tests check routing (`:as-of` timestamp, an unplannable rule body, a three-argument call and a write transaction stay on the executor) and derived rows read across batches before and after a checkpoint; `relation.rs` unit tests check row identity and the `Old` / `Delta` / `Full` ranges. +- **Query memory limit** (`tests/memory_limit_test.rs`, 7 tests; #549): `OpenOptions::query_memory_limit` is off by default and set by its builder; `QRY-012` through `execute`, a cursor's first pull, a prepared query and a rule query (from `execute`, and from `query` when the rules run at open); the database answers after a query fails; a write transaction's query is counted until it stages a write, then runs uncounted on the executor; a prepared rule query uses the database's `max_derived_facts`. Engine unit tests (`src/query/engine/tests.rs`, 7 more): `HashJoin`, `AntiJoin`, `Union`, `Aggregate` and `Window` charge while they hold state and the meter is back at 0 after a drain and after an early drop; `QRY-012` names the holder over the limit (each operator, `IdSpace`, `Recursive`, `Distinct` and `Relations`), and its allocator form through the `try_reserve` test hook; a cursor returns rows, then `QRY-012`, then nothing; `rewind` and `close` release; the planner builds a keyless join on the side with the smaller product estimate (#575's shape, a selective outer side, a tie, reordering off). `meter.rs` (4 unit tests) checks charge, release, drop, peak and the allocator form. - **Join rules** (`tests/join_rules_test.rs`, 10 tests; #545): a join on a float value pairs `0.0` with `-0.0`, through the hash key and as a shared variable, and a float constant still matches within epsilon; a variable bound to a keyword by one pattern and to the ref of the same entity by another returns the kind from the first pattern in `:where` text order, when the planner runs the patterns in another order, through the attribute position, before and after a rule call, and with a repeated pattern; an expression binding unifies with a pattern binding the same variable, and the first binder in the text, pattern or expression, gives the value (#596); a pseudo-attribute pattern never gives a variable its value, even when it runs first (#606; the plan-independence matrix checks it with reordering off). Under the `test-oracle` feature the joins among them also run on the streaming engine. A unit test checks that `-0.0` and `0.0` hash alike. - **Pseudo-attribute sources** (`tests/pseudo_source_test.rs`, 12 tests; #594): a per-fact pseudo-attribute reads the nearest earlier pattern in the text with the same entity term (#594's example in both text orders), two pseudo-attributes share a source, `[:alice ?a _]` gives one row per fact, constant and bound value terms check, `:alice` and its UUID are one term while `?e` and `:alice` are not, PRS-081 for a pattern after it, alone, `_`/`?_x` entities, another entity's pattern and a rule call; a `not` body reads the outer fact (and a source inside the body), `not-join` crosses for a listed variable only, `or` branches read the outer fact and never a sibling, `or-join`, closed rule bodies, `$slot`s by name at prepare time, and `:db/valid-at` once per fact. Parser unit tests check the hidden variables (`?#.`), the join variable a crossed `not-join` gains, and the PRS-081 text; an optimizer test places a pseudo-attribute pattern after its source and the pattern binding its value; matcher tests read the hidden variable, a substituted integer, and nothing without a source; the engine tests run the sourced shapes and check PRS-081 for the old fallback shapes. The plan-independence matrix gains eleven pseudo-attribute shapes. - **Negation equality** (`tests/negation_equality_test.rs`, 5 tests; #546): a value a `not` / `not-join` body takes from the outer row compares by join equality on every path (exclusion set, per-row body with an expression, a query that invokes a rule, a rule body): `1e-20` and `2e-20` differ, `0.0` equals `-0.0`, a keyword imported into an entity position equals the ref, and a float literal in the body still matches within `f64::EPSILON`; through `execute` and a cursor, in memory and after a checkpoint. Engine unit tests (`src/query/engine/tests.rs`, 6 more) run every negation shape (hashed and correlated bodies, keys on entity, value and attribute positions, floats, keywords and refs, long strings, bodies reading an imported variable, variable-free bodies, per-fact pseudo-attributes and `:db/valid-at` in bodies, deferred and repeated negations) at six temporal settings with each body form forced and reordering on and off, in memory and on file before and after checkpoints, against the executor; and check the form the planner picks, routing, multiplicity, failing expressions and unknown predicates in bodies, and that a hashed body is read once while a correlated one probes once per outer row. Optimizer unit tests cover `plan_seeded` and the `SUBPLANS` switch. diff --git a/docs/superpowers/plans/2026-10-21-549-memory-limit.md b/docs/superpowers/plans/2026-10-21-549-memory-limit.md new file mode 100644 index 0000000000..94b3946249 --- /dev/null +++ b/docs/superpowers/plans/2026-10-21-549-memory-limit.md @@ -0,0 +1,138 @@ +# Query memory accounting and the optional limit (#549) — Plan + +Spec: `docs/superpowers/specs/2026-10-21-query-memory-limit-design.md` (merged as #674). PRs +target `v3`. None uses a closing keyword for #473 or #575; #549 closes by hand after PR 2. + +| PR | Steps | Branch | +|---|---|---| +| 1 | 1–10: meter, accounting, `QRY-012`, the option, keyless build side (spec §3–§6.1) | `feat/549-memory-limit` | +| 2 | 11–13: acceptance tests and measurement (spec §6.2) | `feat/549-acceptance` | +| Bindings | 14: the option and `QRY-012` on each binding's `v3` branch (spec §5) | per binding | + +Each PR leaves `v3` with no unused code and updates the test counts and `CHANGELOG.md` for what +it ships. PR 1 has a docs-site PR (`../minigraf-docs`, `@since v3.0.0`) for the option and the +error, merged after PR 1. + +## Design decisions not fixed by the spec + +1. **`Meter` and `Held`** live in a new `src/query/engine/meter.rs`. + `Meter { limit: usize, used: AtomicUsize, peak: AtomicUsize }`, shared as `Arc`. + Each holder owns a `Held { meter: Arc, op: &'static str, bytes: usize }`: + `charge(n) -> Result<()>` (spec §3.1 steps 1–2, saturating arithmetic, `peak` by + `fetch_max`), `uncharge(n)` (an entry let go), `release()` (subtract `bytes`, set it to 0), + and `Drop` calls `release`. So an operator's `Drop` needs no code of its own, and `rewind` + and `close` call `release` where they clear their tables. `peak` is for tests and PR 2's + figures; nothing public reads it. +2. **The allocator form.** `TryReserveError` does not expose the size it asked for on stable + Rust, so the message's `{n}` is the estimate `entry × max(capacity, 1)`: the bytes the + container's doubling would have added. `Held::reserve(charged, refused, r)` turns + `r: Result<(), TryReserveError>` into `QRY-012` and uncharges `charged` on failure. + Under `cfg(test)`, a thread-local `FAIL_RESERVE: Cell>` makes the + next `reserve` of that `op` fail (spec §6.2's test hook). +3. **How the meter reaches holders.** `build(source, steps, &Arc)` passes it to every + operator constructor, and so to `not` bodies, `or` branches and correlated sub-plans, + which `build` builds. `IdSpace::new(keys, meter)`, `Relations::new(iids, meter)`, and + `recursive::heads` / `know_stored` take a local `Held` that drops on return. `Stream` + keeps the `Arc` (and `Stream::meter()` under `cfg(test)`). `engine::open` takes the + limit; `recursive::Limits` gains `query_memory: usize` for `open_rules`. +4. **Executor plumbing.** `DatalogExecutor` is not public API (`mod query` is private), so + `set_limits` becomes `set_limits(max_derived_facts, query_memory_limit)` at its four + `db.rs` call sites, with a `query_memory_limit` field defaulting to `usize::MAX`, copied + by `oracle()`. +5. **`Stream::close`** closes the root (releasing every operator), then empties the + `IdSpace` (provisional and DICT maps, `IdSpace::release`) and drops the `Relations`, so + the meter is 0 after a drain, an early close, an error, and a dropped cursor. +6. **Holders added to the spec's table** (§3.2 says every holder of more than one batch + counts; these were missed). Listed here as deviations from the approved spec: + - `Relations::know`: each stored fact's identity key and its hash entry. `know_stored` + inserts one per stored fact of an evaluated attribute, which can be every fact. + - `sum-distinct`: each new member of `Agg::SumDistinct`'s set, as `count-distinct`'s + (`size_of::()`, the string's length, `HASH_ENTRY_OVERHEAD`). `Agg` gains + `pub(crate) fn would_add(&self, v: &Value) -> bool` so the charge comes before the + insert. + - Not counted: a UDF accumulator's state (opaque), `min`/`max`'s one held value per + group (inside the fixed `Group` size), and the value columns `aggregate::windows` + returns (the executor's code, freed before `finish` returns). Only the cells `finish` + appends to each row are charged. +7. **Release of buffered output.** `Union`'s `At.rows`, and `Aggregate`'s and `Window`'s + finished rows, are uncharged one row at a time as they go into a batch, so a stream that + has returned most of an answer holds little. +8. **`Counters`** gains `bytes_held: u64`, set from the operator's `Held` when `counters()` + pushes it. A holder with two `Held`s (`IdSpace`) is not an operator and has no counters. +9. **`QRY-012`'s registry text** is `query memory limit exceeded: {}`, the two forms of + spec §4 passed as the tail. +10. **The oracle** (`oracle::check`) accepts `(Err(e), _)` when `e` downcasts to a + `CodedError` with code `QRY-012`, whatever the executor answered. +11. **Keyless build side.** `optimizer::product_cost(&[WhereClause]) -> u64`, beside + `branch_cost`: the saturating product of `pattern_cost` over the patterns, 0 for none. + In `plan.rs`, a `JoinKind::Hash` whose `join.keys` is empty uses it for the outer side + (spec §6.1); the reorder switch still forces the inner side. + +## PR 1 — meter, accounting, `QRY-012`, option + +1. **`meter.rs`** (decisions 1, 2): `Meter`, `Held`, `HASH_ENTRY_OVERHEAD = 16`, + `cell_bytes`, `key_bytes`, `row_bytes`, the test hook. Unit tests: a charge over the + limit is `QRY-012` naming the op and counts nothing; `release` and `Drop` return the + bytes; `peak`; `reserve` failure uncharges and gives the allocator form; `usize::MAX` + never fails. +2. **`ErrorCode::Qry012`** in `src/error.rs` (enum in place of the reserved comment, + `REGISTRY`, the exhaustive category match, `ALL`); `docs/ERROR_REFERENCE.md` row and + section (cause, resolution, example), and the "(QRY-012 is reserved.)" note removed from + `QRY-013`. +3. **Option and plumbing** (decisions 3, 4): `OpenOptions::query_memory_limit` field + (doc: what is counted, engine-only gap until #551, 0 fails any stateful query), builder, + `Default` `usize::MAX`; `set_limits`; `engine::open`/`open_rules`/`Limits`; `build` and + the operator constructors; `IdSpace::new`; `Relations::new`; `Stream::for_test` with an + unlimited meter. +4. **Join, AntiJoin, Union, Distinct** (spec §3.2 rows 1–5): charge before each insert, + `try_reserve(1)` on each container grown (`by_key`, `buckets`, a bucket; `set.keys`; the + branch table, its row vectors, `At.rows`; `seen`), release on `rewind`/`close`. + `AntiJoin`'s and `Union`'s hashed tables survive a rewind today, and so does their charge. +5. **Aggregate and Window** (rows 6–7, decisions 6, 7): groups, `count-distinct` and + `sum-distinct` members, finished rows; held cells and values. +6. **Rule queries** (rows 8–9): `Relations::add` and `know` return `Result` and charge; + callers in `open_rules` and `recursive::evaluate` propagate. `know_stored`'s `stored` and + `heads`' `out`/`seen` charge into a local `Held`. +7. **`IdSpace`** (rows 10–11): one `Held` for provisional ids, one for the DICT cache; + `end_pull` releases the DICT one. `Stream::close` (decision 5). +8. **Oracle** (decision 10) and **keyless build side** (decision 11). +9. **Tests.** In `src/query/engine/tests.rs`: each holder charges on insert and releases on + `rewind` and `close` (the meter's `used` read between pulls); `used` is 0 after a drain, + an early close and an error; `QRY-012` names each operator (`HashJoin`, `AntiJoin`, + `Union`, `Distinct`, `Aggregate`, `Window`, `Relations`, `IdSpace`) at a limit just + below its charge; the allocator form per op through the hook; the keyless build side + (#575 shape builds inner from the second join on; `[?e :name "x"] [?p ?q ?r]` builds + outer; a tie builds inner; reorder off builds inner). New `tests/memory_limit_test.rs` + (in-memory, public API only): default `usize::MAX`, builder; `QRY-012` through + `execute`, `query`, a prepared query and a rule query; a cursor that returned rows gets + the error on the next call and the database then answers another query; a write + transaction's query is not limited (the documented executor gap). +10. **Docs and checks.** `CHANGELOG.md` (Added: the option and `QRY-012`; Changed: keyless + joins build on the side with the smaller product estimate), `CLAUDE.md` (module list: + `meter.rs`; counts), `docs/TEST_COVERAGE.md`. Binary size against the 1260 KiB v3 gate. + Envelope 100K and 1M on the bench machine (idle first), before and after, for the scan, + join and aggregate shapes: the accounting adds an atomic add per insert and must not + move them beyond noise. Codex review (`< /dev/null`), CI green, ask before merge (merge + commit, admin bypass). Docs-site PR `v3/549-memory-limit`. + +## PR 2 — acceptance and measurement + +11. `tests/memory_limit_acceptance_test.rs` (`#![cfg(target_os = "linux")]`, both tests + `#[ignore]`d, peak RSS by resetting `VmHWM` as `recursive_acceptance_test.rs` does): + 1M groups (no limit: 1M rows; limit 32 MiB: `QRY-012` naming `Aggregate`) and #575 at + k = 13 (drain 3^13 rows through `Minigraf::query`, peak RSS < 64 MiB; limit 64 B: + `QRY-012` naming `HashJoin`). Deviation from spec §6.2: an integration test cannot read + the meter's counters, so test 1's limit is fixed below the floor every group costs + (1M × at least 40 bytes, a key and its hash entry) instead of read from a first run. +12. `smoke.yml` job: `cargo test --profile bench --test memory_limit_acceptance_test -- + --ignored` without `test-oracle`. +13. Measured figures: an ignored engine test prints the meter's `peak` for both shapes; + the PR and `docs/` give peak against RSS (spec §3.2's factor of two). Codex review, CI, + ask before merge. Close #549 by hand. + +## Bindings + +14. On each binding's `v3` branch: `query_memory_limit` on every `OpenOptions` record + (UniFFI `usize::MAX` ↔ `i64::MAX`, as `wal_checkpoint_threshold`), and `QRY-012`. + Python, Java, Android, Swift (UniFFI, which break on the new `ErrorCode` until they + regenerate), then Node, WASM, C where they expose `OpenOptions`. diff --git a/src/db.rs b/src/db.rs index 82d3273156..204be45da7 100644 --- a/src/db.rs +++ b/src/db.rs @@ -185,6 +185,23 @@ pub struct OpenOptions { /// `API-014`. Queries, cursors, [`Minigraf::fact_log`], /// [`Minigraf::verify`] and rule registration (which lives in memory) work. pub read_only: bool, + /// The most bytes one query may hold, or `usize::MAX` (the default) for + /// no limit (#549). + /// + /// A query that would hold more fails with `QRY-012` instead, and frees + /// what it held; the database and other queries are unaffected. Each + /// operator that keeps state — a hash join's build side, a negation or + /// `or` table, a distinct set, the groups of an aggregate, the rows of + /// a window, the facts a rule query derives, and the query's entity and + /// ident ids — counts an estimate of its bytes per entry, the same on + /// every platform. Rows passing between operators are not counted, and + /// 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, } #[allow(deprecated)] // `max_results`, kept as an alias until it is removed @@ -198,6 +215,7 @@ impl Default for OpenOptions { allow_unlocked: false, synchronous: SyncMode::Full, read_only: false, + query_memory_limit: usize::MAX, } } } @@ -252,6 +270,14 @@ impl OpenOptions { self } + /// Set the most bytes one query may hold. See + /// [`OpenOptions::query_memory_limit`]. + #[must_use] + pub fn query_memory_limit(mut self, bytes: usize) -> Self { + self.query_memory_limit = bytes; + self + } + /// The limit rule queries run with: the lower of `max_derived_facts` and /// its deprecated alias `max_results` (#553). #[allow(deprecated)] @@ -806,7 +832,10 @@ impl Minigraf { self.inner.rules.clone(), self.inner.functions.clone(), ); - executor.set_limits(self.inner.options.derived_fact_limit()); + executor.set_limits( + self.inner.options.derived_fact_limit(), + self.inner.options.query_memory_limit, + ); executor.set_snapshot(snapshot); executor } @@ -1193,6 +1222,10 @@ impl Minigraf { self.inner.fact_storage.clone(), self.inner.rules.clone(), self.inner.functions.clone(), + ( + self.inner.options.derived_fact_limit(), + self.inner.options.query_memory_limit, + ), ) } @@ -1508,7 +1541,10 @@ impl<'a> WriteTransaction<'a> { self.inner.rules.clone(), self.inner.functions.clone(), ); - executor.set_limits(self.inner.options.derived_fact_limit()); + executor.set_limits( + self.inner.options.derived_fact_limit(), + self.inner.options.query_memory_limit, + ); return executor.execute(cmd); } @@ -1519,7 +1555,10 @@ impl<'a> WriteTransaction<'a> { self.inner.rules.clone(), self.inner.functions.clone(), ); - executor.set_limits(self.inner.options.derived_fact_limit()); + executor.set_limits( + self.inner.options.derived_fact_limit(), + self.inner.options.query_memory_limit, + ); executor.execute(cmd) } @@ -1532,7 +1571,10 @@ impl<'a> WriteTransaction<'a> { self.inner.rules.clone(), self.inner.functions.clone(), ); - executor.set_limits(self.inner.options.derived_fact_limit()); + executor.set_limits( + self.inner.options.derived_fact_limit(), + self.inner.options.query_memory_limit, + ); executor.execute(DatalogCommand::Rule(rule)) } @@ -2298,6 +2340,7 @@ mod tests { allow_unlocked: false, synchronous: SyncMode::Full, read_only: false, + query_memory_limit: usize::MAX, }; let db = Minigraf::open_with_options(&path, opts).unwrap(); assert_eq!(db.inner.options.wal_checkpoint_threshold, 5); diff --git a/src/error.rs b/src/error.rs index ac2d9f3e56..57a5d4294a 100644 --- a/src/error.rs +++ b/src/error.rs @@ -172,7 +172,7 @@ pub(crate) enum ErrorCode { Qry009, Qry010, Qry011, - // QRY-012 is reserved for the query memory limit (#549). + Qry012, Qry013, Int000, Stg001, @@ -1071,6 +1071,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "unknown window function '{}' — register it with register_aggregate() before querying", ErrorCategory::Query, ), + ( + ErrorCode::Qry012, + "QRY-012", + "query memory limit exceeded: {}", + ErrorCategory::Query, + ), ( ErrorCode::Qry013, "QRY-013", @@ -2275,6 +2281,7 @@ mod tests { | ErrorCode::Qry009 | ErrorCode::Qry010 | ErrorCode::Qry011 + | ErrorCode::Qry012 | ErrorCode::Qry013 | ErrorCode::Stg001 | ErrorCode::Stg002 @@ -2536,6 +2543,7 @@ mod tests { ErrorCode::Qry009, ErrorCode::Qry010, ErrorCode::Qry011, + ErrorCode::Qry012, ErrorCode::Qry013, ErrorCode::Stg001, ErrorCode::Stg002, diff --git a/src/query/datalog/aggregate.rs b/src/query/datalog/aggregate.rs index ef923760c9..816d789b98 100644 --- a/src/query/datalog/aggregate.rs +++ b/src/query/datalog/aggregate.rs @@ -442,6 +442,17 @@ impl Agg { }) } + /// Whether [`step`](Self::step) would add `v` to a distinct set, so a + /// caller can count it first (#549). + pub(crate) fn would_add(&self, v: &Value) -> bool { + match self { + Agg::CountDistinct(set) | Agg::SumDistinct(set) => { + !matches!(v, Value::Null) && !set.contains(&canonical(v)) + } + _ => false, + } + } + /// Take one value; `nil` is skipped by every aggregate. pub(crate) fn step(&mut self, v: &Value) { if matches!(v, Value::Null) { diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index ee1c0a4b4a..29b8b6bc8d 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -154,6 +154,8 @@ pub struct DatalogExecutor { functions: Arc>, /// The most facts a rule query may derive, base facts not counted (#553). max_derived_facts: usize, + /// The most bytes an engine query may hold (#549). + query_memory_limit: usize, } impl DatalogExecutor { @@ -167,6 +169,7 @@ impl DatalogExecutor { 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, + query_memory_limit: usize::MAX, } } @@ -186,6 +189,7 @@ impl DatalogExecutor { rules, functions, max_derived_facts: crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS, + query_memory_limit: usize::MAX, } } @@ -204,6 +208,7 @@ impl DatalogExecutor { rules, functions, max_derived_facts: crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS, + query_memory_limit: usize::MAX, } } @@ -237,13 +242,16 @@ impl DatalogExecutor { rules, functions, max_derived_facts, + query_memory_limit: usize::MAX, } } /// Set the most facts a rule query may derive, base facts not counted - /// (`OpenOptions::max_derived_facts`, #553). - pub fn set_limits(&mut self, max_derived_facts: usize) { + /// (`OpenOptions::max_derived_facts`, #553), and the most bytes a query + /// on the engine may hold (`OpenOptions::query_memory_limit`, #549). + pub fn set_limits(&mut self, max_derived_facts: usize, query_memory_limit: usize) { self.max_derived_facts = max_derived_facts; + self.query_memory_limit = query_memory_limit; } /// Read every fact from `snapshot`, so the queries of this executor see @@ -581,16 +589,24 @@ impl DatalogExecutor { check_clauses(&query, ®istry)?; } let snapshot = self.read_snapshot()?; - if let Some(stream) = - crate::query::engine::open(snapshot.clone(), plan, self.functions.clone()) - { + if let Some(stream) = crate::query::engine::open( + snapshot.clone(), + plan, + self.functions.clone(), + self.query_memory_limit, + ) { #[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"))] 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::open( + snapshot.clone(), + plan, + self.functions.clone(), + self.query_memory_limit, + ) }) { crate::query::engine::oracle::check( &again.collect(), @@ -630,6 +646,7 @@ impl DatalogExecutor { let limits = crate::query::engine::Limits { max_iterations: crate::query::datalog::evaluator::DEFAULT_MAX_ITERATIONS, max_derived_facts: self.derived_limit(query), + query_memory: self.query_memory_limit, }; let snapshot = self.read_snapshot()?; let open = |plan| -> Result> { @@ -694,6 +711,7 @@ impl DatalogExecutor { rules: self.rules.clone(), functions: self.functions.clone(), max_derived_facts: self.max_derived_facts, + query_memory_limit: self.query_memory_limit, } } @@ -4256,7 +4274,7 @@ mod tests { rules.clone(), functions.clone(), ); - executor.set_limits(1_000_000); + executor.set_limits(1_000_000, usize::MAX); executor .execute(parse_datalog_command(r#"(rule [(reachable ?x ?y) [?x :edge ?y]])"#).unwrap()) diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index 989b2de9e5..7e630f5540 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -487,6 +487,21 @@ fn pattern_cost(p: &Pattern) -> u64 { } } +/// Estimated size of the join of a slice's patterns when nothing joins them: +/// the product of their `pattern_cost`s, saturating; 0 for no pattern. The +/// engine builds a keyless hash join on its inner pattern when that pattern +/// costs no more than this of the outer patterns (#549 spec §6.1). +pub(crate) fn product_cost(branch: &[WhereClause]) -> u64 { + let mut costs = branch.iter().filter_map(|c| match c { + WhereClause::Pattern(p) => Some(pattern_cost(p)), + _ => None, + }); + let Some(first) = costs.next() else { + return 0; + }; + costs.fold(first, u64::saturating_mul) +} + /// Estimated cost for a body/branch slice — the minimum `pattern_cost` across all /// Pattern clauses, or 0 if the body contains no patterns (expr-only bodies are /// cheap pure computation). diff --git a/src/query/datalog/prepared.rs b/src/query/datalog/prepared.rs index abed73dac7..5108230b79 100644 --- a/src/query/datalog/prepared.rs +++ b/src/query/datalog/prepared.rs @@ -83,6 +83,8 @@ pub struct PreparedQuery { fact_storage: FactStorage, rules: Arc>, functions: Arc>, + /// The database's `max_derived_facts` and `query_memory_limit`. + limits: (usize, usize), } impl std::fmt::Debug for PreparedQuery { @@ -156,6 +158,7 @@ impl PreparedQuery { self.rules.clone(), self.functions.clone(), ); + executor.set_limits(self.limits.0, self.limits.1); executor.set_snapshot(snapshot); Ok((executor, DatalogCommand::Query(filled_query))) } @@ -168,6 +171,7 @@ pub(crate) fn prepare_query( fact_storage: FactStorage, rules: Arc>, functions: Arc>, + limits: (usize, usize), ) -> Result { validate_no_attribute_slots(&query)?; let slot_names = collect_slot_names(&query); @@ -177,6 +181,7 @@ pub(crate) fn prepare_query( fact_storage, rules, functions, + limits, }) } diff --git a/src/query/engine/aggregate.rs b/src/query/engine/aggregate.rs index a8fe9d0799..a23676906a 100644 --- a/src/query/engine/aggregate.rs +++ b/src/query/engine/aggregate.rs @@ -13,12 +13,18 @@ use super::batch::Batch; use super::cell::{Cell, JoinKey, Scalar}; +use super::meter::{ + HASH_ENTRY_OVERHEAD, Held, Meter, cell_bytes, growth, key_bytes, keys_bytes, row_bytes, + value_bytes, +}; use super::project::value; use super::{BATCH_ROWS, Counters, Ctx, Operator}; use crate::graph::types::Value; use crate::query::datalog::aggregate::{Agg, Groups, finish_groups, value_order}; use anyhow::Result; use std::collections::{HashMap, HashSet}; +use std::mem::size_of; +use std::sync::Arc; /// One aggregate of one group. enum Acc { @@ -39,16 +45,30 @@ impl Acc { }) } - fn step(&mut self, cell: &Cell, ctx: &mut Ctx<'_>) -> Result<()> { + /// Take `cell`, counting a new member of a distinct set on `held`. + fn step(&mut self, cell: &Cell, held: &mut Held, ctx: &mut Ctx<'_>) -> Result<()> { if matches!(cell, Cell::Val(Scalar::Null)) { return Ok(()); } match self { Acc::Count(n) => *n = n.saturating_add(1), Acc::CountDistinct(set) => { - set.insert(JoinKey::group(cell)); + let k = JoinKey::group(cell); + if !set.contains(&k) { + let n = key_bytes(&k) + HASH_ENTRY_OVERHEAD; + held.charge(n)?; + let refused = growth(set.capacity(), n); + held.reserve(set.try_reserve(1), n, refused)?; + set.insert(k); + } + } + Acc::Values(agg) => { + let v = value(cell, ctx)?; + if agg.would_add(&v) { + held.charge(value_bytes(&v) + HASH_ENTRY_OVERHEAD)?; + } + agg.step(&v); } - Acc::Values(agg) => agg.step(&value(cell, ctx)?), } Ok(()) } @@ -81,6 +101,10 @@ pub(crate) struct Aggregate { rows: Vec, /// The finished rows, last first, once the input has ended. out: Option>>, + /// The groups (#549 spec §3.2). + held: Held, + /// The finished rows, released as they are returned. + finished: Held, counters: Counters, } @@ -90,6 +114,7 @@ impl Aggregate { groups: Vec, aggs: Vec<(String, usize)>, zero_row: bool, + meter: &Arc, ) -> Self { Aggregate { child, @@ -99,6 +124,8 @@ impl Aggregate { table: HashMap::new(), rows: Vec::new(), out: None, + held: Held::new(meter, "Aggregate"), + finished: Held::new(meter, "Aggregate"), counters: Counters::new("Aggregate"), } } @@ -115,21 +142,37 @@ impl Aggregate { .iter() .map(|&s| JoinKey::group(cell(s, i).unwrap_or(&null))) .collect(); - let at = match self.table.entry(key) { - std::collections::hash_map::Entry::Occupied(e) => *e.get(), - std::collections::hash_map::Entry::Vacant(e) => { + let at = match self.table.get(&key) { + Some(&at) => at, + None => { let accs = self .aggs .iter() .map(|(func, _)| Acc::new(func, ctx)) .collect::>>()?; - let cells = self + let cells: Vec = self .groups .iter() .map(|&s| cell(s, i).unwrap_or(&null).clone()) .collect(); + // The key, its index, the group: its cells and + // accumulators. + let entry = keys_bytes(&key) + size_of::() + HASH_ENTRY_OVERHEAD; + let group = size_of::() + + cells.iter().map(cell_bytes).sum::() + + accs.len() * size_of::(); + let n = entry + group; + self.held.charge(n)?; + let refused = growth(self.table.capacity(), entry) + .saturating_add(growth(self.rows.capacity(), size_of::())); + let reserved = self + .table + .try_reserve(1) + .and_then(|()| self.rows.try_reserve(1)); + self.held.reserve(reserved, n, refused)?; self.rows.push(Group { cells, accs }); - *e.insert(self.rows.len() - 1) + self.table.insert(key, self.rows.len() - 1); + self.rows.len() - 1 } }; let Some(group) = self.rows.get_mut(at) else { @@ -148,7 +191,7 @@ impl Aggregate { } for (acc, (_, slot)) in group.accs.iter_mut().zip(&self.aggs) { if let Some(c) = cell(*slot, i) { - acc.step(c, ctx)?; + acc.step(c, &mut self.held, ctx)?; } } } @@ -176,16 +219,20 @@ impl Aggregate { } self.table.clear(); let funcs: Vec<&str> = self.aggs.iter().map(|(f, _)| f.as_str()).collect(); - let mut rows = Vec::with_capacity(groups.len()); + let mut rows = Vec::new(); for (shown, results) in finish_groups(groups, &funcs)? { - rows.push( - shown - .iter() - .chain(&results) - .map(|v| Cell::of_value(ctx.ids, ctx.keys, v)) - .collect::>>()?, - ); + let row = shown + .iter() + .chain(&results) + .map(|v| Cell::of_value(ctx.ids, ctx.keys, v)) + .collect::>>()?; + let n = row_bytes(&row); + self.finished.charge(n)?; + let refused = growth(rows.capacity(), size_of::>()); + self.finished.reserve(rows.try_reserve(1), n, refused)?; + rows.push(row); } + self.held.release(); rows.reverse(); Ok(rows) } @@ -208,6 +255,7 @@ impl Operator for Aggregate { while batch.len < BATCH_ROWS && let Some(row) = rows.pop() { + self.finished.uncharge(row_bytes(&row)); batch.push(&mut row.into_iter().map(Some).collect::>()); } self.counters.out(&batch); @@ -218,6 +266,8 @@ impl Operator for Aggregate { self.table.clear(); self.rows.clear(); self.out = None; + self.held.release(); + self.finished.release(); self.child.rewind(seed); } @@ -225,11 +275,16 @@ impl Operator for Aggregate { self.table = HashMap::new(); self.rows = Vec::new(); self.out = Some(Vec::new()); + self.held.release(); + self.finished.release(); self.child.close(); } fn counters(&self, out: &mut Vec) { - out.push(self.counters); + out.push(Counters { + bytes_held: (self.held.bytes() + self.finished.bytes()) as u64, + ..self.counters + }); self.child.counters(out); } } diff --git a/src/query/engine/anti.rs b/src/query/engine/anti.rs index c4708943ff..151ee00343 100644 --- a/src/query/engine/anti.rs +++ b/src/query/engine/anti.rs @@ -8,14 +8,19 @@ use super::batch::Batch; use super::cell::{Cell, JoinKey}; +use super::meter::{HASH_ENTRY_OVERHEAD, Held, Meter, growth, keys_bytes}; use super::plan::{Body as Spec, Key}; use super::{Counters, Ctx, Operator, build}; use anyhow::Result; use std::collections::HashSet; +use std::sync::Arc; pub(crate) struct AntiJoin { outer: Box, body: Body, + /// A hashed body's set (#549 spec §3.2), counted as long as the set is + /// kept: until the operator drops. + held: Held, /// `rows_in` counts the outer rows received. counters: Counters, } @@ -42,15 +47,15 @@ struct Set { } impl AntiJoin { - pub(crate) fn new(outer: Box, spec: Spec) -> Self { + pub(crate) fn new(outer: Box, spec: Spec, meter: &Arc) -> Self { let body = match spec { Spec::Correlated { plan, imports } => Body::Correlated { - root: build(plan.source, plan.steps), + root: build(plan.source, plan.steps, meter), imports, seed: Vec::new(), }, Spec::Hashed { plan, keys } => Body::Hashed { - root: build(plan.source, plan.steps), + root: build(plan.source, plan.steps, meter), keys, set: None, }, @@ -58,6 +63,7 @@ impl AntiJoin { AntiJoin { outer, body, + held: Held::new(meter, "AntiJoin"), counters: Counters::new("AntiJoin"), } } @@ -70,7 +76,13 @@ fn cell(batch: &Batch, slot: usize, i: usize) -> Option<&Cell> { impl Body { /// Whether the body has a row for row `i` of `batch`. - fn matches(&mut self, batch: &Batch, i: usize, ctx: &mut Ctx<'_>) -> Result { + fn matches( + &mut self, + batch: &Batch, + i: usize, + held: &mut Held, + ctx: &mut Ctx<'_>, + ) -> Result { match self { Body::Correlated { root, @@ -91,7 +103,7 @@ impl Body { } Body::Hashed { root, keys, set } => { if set.is_none() { - *set = Some(collect(root.as_mut(), keys, ctx)?); + *set = Some(collect(root.as_mut(), keys, held, ctx)?); } let Some(set) = set else { return Ok(false); @@ -129,7 +141,12 @@ impl Body { } /// Every row of a hashed body, as the keys of `keys`' inner slots. -fn collect(root: &mut dyn Operator, keys: &[Key], ctx: &mut Ctx<'_>) -> Result { +fn collect( + root: &mut dyn Operator, + keys: &[Key], + held: &mut Held, + ctx: &mut Ctx<'_>, +) -> Result { let mut set = Set { keys: HashSet::new(), any: false, @@ -151,6 +168,13 @@ fn collect(root: &mut dyn Operator, keys: &[Key], ctx: &mut Ctx<'_>) -> Result 0 { @@ -185,7 +209,10 @@ impl Operator for AntiJoin { } fn counters(&self, out: &mut Vec) { - out.push(self.counters); + out.push(Counters { + bytes_held: self.held.bytes() as u64, + ..self.counters + }); self.body.root().counters(out); self.outer.counters(out); } diff --git a/src/query/engine/distinct.rs b/src/query/engine/distinct.rs index c32e8c7e13..3007ae3a5d 100644 --- a/src/query/engine/distinct.rs +++ b/src/query/engine/distinct.rs @@ -5,24 +5,28 @@ use super::batch::Batch; use super::cell::{Cell, JoinKey}; +use super::meter::{HASH_ENTRY_OVERHEAD, Held, Meter, growth, keys_bytes}; use super::{Counters, Ctx, Operator}; use anyhow::Result; use std::collections::HashSet; +use std::sync::Arc; pub(crate) struct Distinct { child: Box, slots: Vec, /// The rows returned since the last rewind. seen: HashSet>, + held: Held, counters: Counters, } impl Distinct { - pub(crate) fn new(child: Box, slots: Vec) -> Self { + pub(crate) fn new(child: Box, slots: Vec, meter: &Arc) -> Self { Distinct { child, slots, seen: HashSet::new(), + held: Held::new(meter, "Distinct"), counters: Counters::new("Distinct"), } } @@ -39,6 +43,13 @@ impl Distinct { }; key.push(k); } + if self.seen.contains(&key) { + return Ok(false); + } + let n = keys_bytes(&key) + HASH_ENTRY_OVERHEAD; + self.held.charge(n)?; + let refused = growth(self.seen.capacity(), n); + self.held.reserve(self.seen.try_reserve(1), n, refused)?; Ok(self.seen.insert(key)) } } @@ -62,16 +73,21 @@ impl Operator for Distinct { fn rewind(&mut self, seed: &[Cell]) { self.seen.clear(); + self.held.release(); self.child.rewind(seed); } fn close(&mut self) { self.seen = HashSet::new(); + self.held.release(); self.child.close(); } fn counters(&self, out: &mut Vec) { - out.push(self.counters); + out.push(Counters { + bytes_held: self.held.bytes() as u64, + ..self.counters + }); self.child.counters(out); } } diff --git a/src/query/engine/ids.rs b/src/query/engine/ids.rs index 5e49bb1156..08f1caff6d 100644 --- a/src/query/engine/ids.rs +++ b/src/query/engine/ids.rs @@ -13,6 +13,7 @@ //! already looked up every row's ids in its first pull, and holds the whole //! answer anyway (#547). +use super::meter::{HASH_ENTRY_OVERHEAD, Held, Meter, growth}; use crate::error::{ErrorCode, err_coded}; use crate::graph::types::EntityId; use crate::query::datalog::matcher::edn_to_entity_id; @@ -20,6 +21,7 @@ use crate::query::datalog::types::EdnValue; use crate::storage::KeySource; use anyhow::Result; use std::collections::HashMap; +use std::mem::size_of; use std::sync::Arc; pub(crate) struct IdSpace { @@ -32,6 +34,9 @@ pub(crate) struct IdSpace { provisional: Maps, /// DICT lookups, until the next pull. dict: Maps, + /// What `provisional` and `dict` hold (#549 spec §3.2). + held_provisional: Held, + held_dict: Held, } #[derive(Default)] @@ -45,7 +50,7 @@ struct Maps { } impl IdSpace { - pub(crate) fn new(keys: Option<&dyn KeySource>) -> Self { + pub(crate) fn new(keys: Option<&dyn KeySource>, meter: &Arc) -> Self { let (eids, iids) = keys.map_or((0, 0), |k| { let (e, i) = k.next_ids(); (e, u64::from(i)) @@ -57,12 +62,45 @@ impl IdSpace { next_iid: iids, provisional: Maps::default(), dict: Maps::default(), + held_provisional: Held::new(meter, "IdSpace"), + held_dict: Held::new(meter, "IdSpace"), } } /// Forget the DICT lookups of the last pull. pub(crate) fn end_pull(&mut self) { self.dict = Maps::default(); + self.held_dict.release(); + } + + /// Forget every id, when the query ends. + pub(crate) fn release(&mut self) { + self.end_pull(); + self.provisional = Maps::default(); + self.held_provisional.release(); + } + + /// Count an entry of `bytes` about to go into the maps that hold + /// provisional ids or DICT lookups, and make room in `grow`. + fn charge( + &mut self, + provisional: bool, + bytes: usize, + grow: impl FnOnce( + &mut Maps, + ) -> ( + std::result::Result<(), std::collections::TryReserveError>, + usize, + ), + ) -> Result<()> { + let (maps, held) = if provisional { + (&mut self.provisional, &mut self.held_provisional) + } else { + (&mut self.dict, &mut self.held_dict) + }; + held.charge(bytes)?; + let (r, refused) = grow(maps); + held.reserve(r, bytes, refused) } /// DICT lookups cached now. @@ -95,6 +133,7 @@ impl IdSpace { (e, true) } }; + self.charge(provisional, EID_ENTRY, grow_eid)?; let maps = self.maps(provisional); maps.eid_by_uuid.insert(*uuid, e); maps.uuid_by_eid.insert(e, *uuid); @@ -116,6 +155,7 @@ impl IdSpace { (i, true) } }; + self.charge(provisional, iid_entry(name), grow_iid)?; let name: Arc = Arc::from(name); let maps = self.maps(provisional); maps.iid_by_name.insert(name.clone(), i); @@ -136,6 +176,7 @@ impl IdSpace { )); }; let u = k.uuid_of(eid)?; + self.charge(false, EID_ENTRY, grow_eid)?; self.dict.uuid_by_eid.insert(eid, u); self.dict.eid_by_uuid.insert(u, eid); Ok(u) @@ -156,6 +197,10 @@ impl IdSpace { let e = self.eid(keys, &uuid)?; // Kept as long as the shorter-lived of the two ids. let provisional = iid >= self.dict_iids && e >= self.dict_eids; + self.charge(provisional, KEYWORD_ENTRY, |m| { + let cap = m.eid_by_keyword.capacity(); + (m.eid_by_keyword.try_reserve(1), growth(cap, KEYWORD_ENTRY)) + })?; self.maps(provisional).eid_by_keyword.insert(iid, e); Ok(e) } @@ -179,19 +224,59 @@ impl IdSpace { )); }; let n: Arc = Arc::from(k.ident_of(i)?); + self.charge(false, iid_entry(&n), grow_iid)?; self.dict.name_by_iid.insert(iid, n.clone()); self.dict.iid_by_name.insert(n.clone(), iid); Ok(n) } } +/// An entity in both directions of its map. +const EID_ENTRY: usize = 2 * (size_of::() + size_of::() + HASH_ENTRY_OVERHEAD); + +/// A keyword's entity. +const KEYWORD_ENTRY: usize = 2 * size_of::() + HASH_ENTRY_OVERHEAD; + +/// An ident in both directions of its map, with its name. +fn iid_entry(name: &str) -> usize { + 2 * (size_of::>() + size_of::() + HASH_ENTRY_OVERHEAD) + name.len() +} + +fn grow_eid( + m: &mut Maps, +) -> ( + std::result::Result<(), std::collections::TryReserveError>, + usize, +) { + let cap = m.eid_by_uuid.capacity(); + let r = m + .eid_by_uuid + .try_reserve(1) + .and_then(|()| m.uuid_by_eid.try_reserve(1)); + (r, growth(cap, EID_ENTRY)) +} + +fn grow_iid( + m: &mut Maps, +) -> ( + std::result::Result<(), std::collections::TryReserveError>, + usize, +) { + let cap = m.iid_by_name.capacity(); + let r = m + .iid_by_name + .try_reserve(1) + .and_then(|()| m.name_by_iid.try_reserve(1)); + (r, growth(cap, iid_entry(""))) +} + #[cfg(test)] mod tests { use super::*; #[test] fn provisional_ids_outlive_a_pull() { - let mut ids = IdSpace::new(None); + let mut ids = IdSpace::new(None, &Meter::unlimited()); 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(); @@ -208,7 +293,7 @@ mod tests { /// UUID was met first as an entity or not. #[test] fn keyword_eid_is_the_named_entitys_id() { - let mut ids = IdSpace::new(None); + let mut ids = IdSpace::new(None, &Meter::unlimited()); let named = uuid::Uuid::new_v5(&uuid::Uuid::NAMESPACE_OID, b":alice"); let e = ids.eid(None, &named).unwrap(); let k = ids.iid(None, ":alice").unwrap(); diff --git a/src/query/engine/join.rs b/src/query/engine/join.rs index 8ba893a33a..1727ce3f4d 100644 --- a/src/query/engine/join.rs +++ b/src/query/engine/join.rs @@ -9,11 +9,14 @@ use super::batch::Batch; use super::cell::{Cell, JoinKey, join_eq}; +use super::meter::{HASH_ENTRY_OVERHEAD, Held, Meter, growth, keys_bytes, row_bytes}; use super::plan::{JoinKind, JoinSpec, Key}; use super::scan::Scan; use super::{BATCH_ROWS, Counters, Ctx, Operator}; use anyhow::Result; use std::collections::HashMap; +use std::mem::size_of; +use std::sync::Arc; type Row = Vec; @@ -26,6 +29,8 @@ pub(crate) struct Join { replace: Vec<(usize, usize)>, outer_width: usize, state: State, + /// The build side's table (#549 spec §3.2). + held: Held, /// `rows_in` counts the outer rows received. counters: Counters, } @@ -74,7 +79,7 @@ enum Side { } impl Join { - pub(crate) fn new(outer: Box, spec: JoinSpec) -> Self { + pub(crate) fn new(outer: Box, spec: JoinSpec, meter: &Arc) -> Self { let op = match spec.kind { JoinKind::Probe(_) => "IndexNestedLoopJoin", JoinKind::Hash { .. } => "HashJoin", @@ -88,6 +93,7 @@ impl Join { replace: spec.replace, outer_width: spec.outer_width, state: State::Start, + held: Held::new(meter, op), counters: Counters::new(op), } } @@ -153,12 +159,33 @@ impl Join { let Some(key) = self.key(&row, side, ctx)? else { continue; }; - let next = table.buckets.len(); - let b = *table.by_key.entry(key).or_insert(next); - if b == next { - table.buckets.push(Vec::new()); - } + let found = table.by_key.get(&key).copied(); + // A new key's bucket: the key, its index, the bucket's + // header; then the row's cells. + let bucket_bytes = keys_bytes(&key) + + size_of::() + + size_of::>() + + HASH_ENTRY_OVERHEAD; + let n = row_bytes(&row) + if found.is_none() { bucket_bytes } else { 0 }; + self.held.charge(n)?; + let b = match found { + Some(b) => b, + None => { + let refused = growth(table.by_key.capacity(), bucket_bytes); + let reserved = table + .by_key + .try_reserve(1) + .and_then(|()| table.buckets.try_reserve(1)); + self.held.reserve(reserved, n, refused)?; + let next = table.buckets.len(); + table.by_key.insert(key, next); + table.buckets.push(Vec::new()); + next + } + }; if let Some(bucket) = table.buckets.get_mut(b) { + let refused = growth(bucket.capacity(), size_of::()); + self.held.reserve(bucket.try_reserve(1), n, refused)?; bucket.push(row); } } @@ -364,18 +391,23 @@ impl Operator for Join { fn rewind(&mut self, seed: &[Cell]) { self.state = State::Start; + self.held.release(); self.outer.rewind(seed); self.inner.rewind(&[]); } fn close(&mut self) { self.state = State::Done; + self.held.release(); self.outer.close(); self.inner.close(); } fn counters(&self, out: &mut Vec) { - out.push(self.counters); + out.push(Counters { + bytes_held: self.held.bytes() as u64, + ..self.counters + }); self.inner.counters(out); self.outer.counters(out); } diff --git a/src/query/engine/meter.rs b/src/query/engine/meter.rs new file mode 100644 index 0000000000..7261416aa6 --- /dev/null +++ b/src/query/engine/meter.rs @@ -0,0 +1,273 @@ +//! The bytes a query holds (#549 spec §3): one [`Meter`] per query, shared +//! by every holder of its state, each through a [`Held`]. +//! +//! A holder charges an entry's estimated bytes before it inserts the entry, +//! then grows its container with `try_reserve`, and releases what it holds +//! when it rewinds, closes or drops. The estimate is per entry (spec §3.2), +//! so the count is the same on every target. + +use super::cell::{Cell, JoinKey, Scalar}; +use crate::error::{ErrorCode, err_coded}; +use crate::graph::types::Value; +use anyhow::Result; +use std::collections::TryReserveError; +use std::mem::size_of; +use std::sync::Arc; +use std::sync::atomic::{AtomicUsize, Ordering}; + +/// What a hash table entry costs beyond its key and value: the control +/// byte, and spare capacity at hashbrown's 7/8 load factor, rounded up. +pub(crate) const HASH_ENTRY_OVERHEAD: usize = 16; + +/// The limit of one query, and the bytes its holders count now. +#[derive(Debug)] +pub(crate) struct Meter { + limit: usize, + used: AtomicUsize, + /// The most `used` has been, for tests and measurement. + peak: AtomicUsize, +} + +impl Meter { + pub(crate) fn new(limit: usize) -> Arc { + Arc::new(Meter { + limit, + used: AtomicUsize::new(0), + peak: AtomicUsize::new(0), + }) + } + + /// A meter with no limit. + #[cfg(test)] + pub(crate) fn unlimited() -> Arc { + Meter::new(usize::MAX) + } + + #[cfg(test)] + pub(crate) fn used(&self) -> usize { + // A query runs on one thread at a time (spec §3.1). + self.used.load(Ordering::Relaxed) + } + + #[cfg(test)] + pub(crate) fn peak(&self) -> usize { + self.peak.load(Ordering::Relaxed) + } +} + +/// What one holder counts on its query's meter. +pub(crate) struct Held { + meter: Arc, + op: &'static str, + bytes: usize, +} + +impl Held { + pub(crate) fn new(meter: &Arc, op: &'static str) -> Self { + Held { + meter: meter.clone(), + op, + bytes: 0, + } + } + + /// The bytes this holder counts now. + pub(crate) fn bytes(&self) -> usize { + self.bytes + } + + /// Count `n` more bytes, or `QRY-012` and count nothing when the query + /// would hold more than its limit. + pub(crate) fn charge(&mut self, n: usize) -> Result<()> { + let m = &*self.meter; + let used = m.used.load(Ordering::Relaxed); + if used.saturating_add(n) > m.limit { + return Err(err_coded!( + ErrorCode::Qry012, + format!( + "{} needs {n} more bytes and the query already holds {used} of its {}-byte limit", + self.op, m.limit + ) + )); + } + let now = used.saturating_add(n); + m.used.store(now, Ordering::Relaxed); + m.peak.fetch_max(now, Ordering::Relaxed); + self.bytes = self.bytes.saturating_add(n); + Ok(()) + } + + /// Stop counting `n` of this holder's bytes: an entry it let go. + pub(crate) fn uncharge(&mut self, n: usize) { + let n = n.min(self.bytes); + self.bytes -= n; + let m = &*self.meter; + m.used.store( + m.used.load(Ordering::Relaxed).saturating_sub(n), + Ordering::Relaxed, + ); + } + + /// Stop counting every byte of this holder. + pub(crate) fn release(&mut self) { + self.uncharge(self.bytes); + } + + /// The result of growing a container with `try_reserve(1)`. A refusal + /// is `QRY-012` (allocator form) and takes back the `charged` bytes; + /// `refused` estimates what the container asked for, as `TryReserveError` + /// does not say on stable Rust. + pub(crate) fn reserve( + &mut self, + r: std::result::Result<(), TryReserveError>, + charged: usize, + refused: usize, + ) -> Result<()> { + #[cfg(test)] + let r = if FAIL_RESERVE.with(|f| f.get() == Some(self.op)) { + Vec::::new().try_reserve(usize::MAX) + } else { + r + }; + if r.is_err() { + self.uncharge(charged); + return Err(err_coded!( + ErrorCode::Qry012, + format!("the allocator refused {refused} bytes for {}", self.op) + )); + } + Ok(()) + } +} + +impl Drop for Held { + fn drop(&mut self) { + self.release(); + } +} + +#[cfg(test)] +thread_local! { + /// Makes every [`Held::reserve`] of this op fail while set (spec §6.2); + /// a query runs on the engine twice under the oracle. + pub(crate) static FAIL_RESERVE: std::cell::Cell> = + const { std::cell::Cell::new(None) }; +} + +/// What growing a container of `capacity` entries of `entry` bytes would +/// ask for: its doubling. +pub(crate) fn growth(capacity: usize, entry: usize) -> usize { + entry.saturating_mul(capacity.max(1)) +} + +/// A cell and the heap bytes of its string. +pub(crate) fn cell_bytes(c: &Cell) -> usize { + size_of::() + + match c { + Cell::Val(Scalar::Str(s)) => s.len(), + _ => 0, + } +} + +/// A row's cells and its vector's header. +pub(crate) fn row_bytes(row: &[Cell]) -> usize { + size_of::>() + row.iter().map(cell_bytes).sum::() +} + +/// A join key and the heap bytes of its string. +pub(crate) fn key_bytes(k: &JoinKey) -> usize { + size_of::() + + match k { + JoinKey::Str(s) => s.len(), + _ => 0, + } +} + +/// A key of several cells and its vector's header. +pub(crate) fn keys_bytes(key: &[JoinKey]) -> usize { + size_of::>() + key.iter().map(key_bytes).sum::() +} + +/// A value and the heap bytes of its string. +pub(crate) fn value_bytes(v: &Value) -> usize { + size_of::() + + match v { + Value::String(s) | Value::Keyword(s) => s.len(), + _ => 0, + } +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::error::CodedError; + + fn code(e: &anyhow::Error) -> Option { + e.downcast_ref::().map(CodedError::code) + } + + #[test] + fn charge_over_the_limit_counts_nothing() { + let meter = Meter::new(100); + let mut a = Held::new(&meter, "HashJoin"); + a.charge(60).unwrap(); + let err = a.charge(41).unwrap_err(); + assert!(code(&err) == Some(ErrorCode::Qry012), "QRY-012"); + let text = err.to_string(); + assert!(text.contains("HashJoin needs 41 more bytes"), "{text}"); + assert!(text.contains("holds 60 of its 100-byte limit"), "{text}"); + assert_eq!(meter.used(), 60); + assert_eq!(a.bytes(), 60); + a.charge(40).unwrap(); + assert_eq!(meter.used(), 100); + } + + #[test] + fn release_and_drop_give_the_bytes_back() { + let meter = Meter::new(1000); + let mut a = Held::new(&meter, "Distinct"); + let mut b = Held::new(&meter, "Aggregate"); + a.charge(300).unwrap(); + b.charge(200).unwrap(); + a.uncharge(100); + assert_eq!(meter.used(), 400); + a.uncharge(10_000); + assert_eq!((a.bytes(), meter.used()), (0, 200), "never below 0"); + b.charge(50).unwrap(); + drop(b); + assert_eq!(meter.used(), 0); + assert_eq!(meter.peak(), 500); + a.charge(10).unwrap(); + a.release(); + assert_eq!(meter.used(), 0); + } + + #[test] + fn a_refused_reserve_is_the_allocator_form() { + let meter = Meter::unlimited(); + let mut a = Held::new(&meter, "Window"); + a.charge(64).unwrap(); + a.reserve(Ok(()), 64, 128).unwrap(); + assert_eq!(meter.used(), 64); + FAIL_RESERVE.with(|f| f.set(Some("Window"))); + let err = a.reserve(Ok(()), 64, 128).unwrap_err(); + assert!(code(&err) == Some(ErrorCode::Qry012), "QRY-012"); + assert!( + err.to_string() + .contains("the allocator refused 128 bytes for Window"), + "allocator form" + ); + assert_eq!(meter.used(), 0, "the charge is taken back"); + FAIL_RESERVE.with(|f| f.set(None)); + a.reserve(Ok(()), 0, 0).unwrap(); + } + + #[test] + fn no_limit_never_fails() { + let meter = Meter::unlimited(); + let mut a = Held::new(&meter, "Union"); + a.charge(usize::MAX).unwrap(); + a.charge(1).unwrap(); + assert_eq!(meter.used(), usize::MAX); + } +} diff --git a/src/query/engine/mod.rs b/src/query/engine/mod.rs index 3bbe5e5d94..957b62b432 100644 --- a/src/query/engine/mod.rs +++ b/src/query/engine/mod.rs @@ -14,6 +14,7 @@ mod distinct; mod filter; mod ids; mod join; +mod meter; #[cfg(any(test, feature = "test-oracle"))] pub(crate) mod oracle; mod plan; @@ -36,6 +37,7 @@ use crate::storage::{CommittedReader, KeySource}; use anyhow::Result; use batch::Batch; use ids::IdSpace; +pub(crate) use meter::Meter; pub(crate) use plan::{Plan, plan, plan_rules}; pub(crate) use recursive::Limits; use std::sync::{Arc, RwLock}; @@ -63,13 +65,14 @@ pub(crate) struct Ctx<'a> { } /// What one operator has done (spec §6.3): rows it read or received, rows -/// and batches it passed on. +/// and batches it passed on, and the bytes it holds (#549). #[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, + pub(crate) bytes_held: u64, } impl Counters { @@ -110,6 +113,10 @@ pub(crate) struct Stream { /// registered (`INT-040`), so the answer does not change between pulls. functions: Arc>, root: Box, + /// The bytes the query's holders count (#549); each holder keeps its + /// own reference, so the stream keeps one for tests only. + #[cfg(test)] + meter: Arc, /// The column of each `:find` element in the root's rows. find: Vec, vars: Vec, @@ -133,19 +140,22 @@ impl std::fmt::Debug for Stream { } } -/// Open `plan` over `snapshot`, or `None` when the snapshot's committed -/// reader has no keys (a test reader) and the executor must run it. +/// Open `plan` over `snapshot`, holding at most `memory_limit` bytes, or +/// `None` when the snapshot's committed reader has no keys (a test reader) +/// and the executor must run it. pub(crate) fn open( snapshot: Snapshot, plan: Plan, functions: Arc>, + memory_limit: usize, ) -> Option { let keys = match &snapshot.committed { Some(reader) => Some(reader.key_source()?), None => None, }; - let ids = IdSpace::new(keys); - Some(stream(snapshot, ids, plan, functions, None)) + let meter = Meter::new(memory_limit); + let ids = IdSpace::new(keys, &meter); + Some(stream(snapshot, ids, plan, functions, None, meter)) } /// Open the rule query `plan` over `snapshot`: derive its relations, with @@ -158,6 +168,7 @@ pub(crate) fn open_rules( functions: Arc>, limits: recursive::Limits, ) -> Result> { + let meter = Meter::new(limits.query_memory); let (ids, relations) = { let keys = match &snapshot.committed { Some(reader) => match reader.key_source() { @@ -166,21 +177,21 @@ pub(crate) fn open_rules( }, None => None, }; - let mut ids = IdSpace::new(keys); + let mut ids = IdSpace::new(keys, &meter); let iids = plan .evaluated .attrs .iter() .map(|a| ids.iid(keys, a)) .collect::>>()?; - let mut rels = relation::Relations::new(iids); + let mut rels = relation::Relations::new(iids, &meter); for (e, a, v) in seeds { if let Some(&rel) = plan.evaluated.by_attr.get(a) { let row = [ cell::Cell::Eid(ids.eid(keys, e)?), cell::Cell::of_value(&mut ids, keys, v)?, ]; - rels.add(rel, row); + rels.add(rel, row)?; } } rels.end_round(); @@ -192,7 +203,7 @@ pub(crate) fn open_rules( keys, functions: &functions, }; - recursive::evaluate(&plan, &mut rels, &reads, &mut ids, limits)?; + recursive::evaluate(&plan, &mut rels, &reads, &mut ids, limits, &meter)?; (ids, rels) }; Ok(Some(stream( @@ -201,6 +212,7 @@ pub(crate) fn open_rules( plan.body, functions, Some(relations), + meter, ))) } @@ -211,6 +223,7 @@ fn stream( plan: Plan, functions: Arc>, relations: Option, + meter: Arc, ) -> Stream { let Plan { source, @@ -219,12 +232,14 @@ fn stream( vars, } = plan; let hold_ids = steps.iter().any(|s| matches!(s, plan::Step::Window { .. })); - let root = build(source, steps); + let root = build(source, steps, &meter); Stream { snapshot, ids, functions, root, + #[cfg(test)] + meter, find, vars, project: Counters::new("Project"), @@ -234,25 +249,32 @@ fn stream( } } -/// The operator tree of a plan's source and steps. -pub(crate) fn build(source: plan::Source, steps: Vec) -> Box { +/// The operator tree of a plan's source and steps, its holders counting on +/// `meter`. +pub(crate) fn build( + source: plan::Source, + steps: Vec, + meter: &Arc, +) -> Box { let mut root: Box = match source { plan::Source::Scan(spec) => Box::new(scan::Scan::new(spec)), plan::Source::Seed => Box::new(seed::Seed::new()), }; for step in steps { root = match step { - plan::Step::Join(spec) => Box::new(join::Join::new(root, spec)), - plan::Step::Anti(body) => Box::new(anti::AntiJoin::new(root, body)), - plan::Step::Union(branches) => Box::new(union::Union::new(root, branches)), - plan::Step::Distinct(slots) => Box::new(distinct::Distinct::new(root, slots)), + plan::Step::Join(spec) => Box::new(join::Join::new(root, spec, meter)), + plan::Step::Anti(body) => Box::new(anti::AntiJoin::new(root, body, meter)), + plan::Step::Union(branches) => Box::new(union::Union::new(root, branches, meter)), + plan::Step::Distinct(slots) => Box::new(distinct::Distinct::new(root, slots, meter)), plan::Step::Aggregate { groups, aggs, zero_row, - } => Box::new(aggregate::Aggregate::new(root, groups, aggs, zero_row)), + } => Box::new(aggregate::Aggregate::new( + root, groups, aggs, zero_row, meter, + )), plan::Step::Window { find, named, keep } => { - Box::new(window::Window::new(root, find, named, keep)) + Box::new(window::Window::new(root, find, named, keep, meter)) } step => Box::new(filter::Apply::new(root, step)), }; @@ -264,11 +286,13 @@ 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 { + let meter = Meter::unlimited(); Stream { snapshot, - ids: IdSpace::new(None), + ids: IdSpace::new(None, &meter), functions: Arc::new(RwLock::new(FunctionRegistry::with_builtins())), root, + meter, find: vec![0], vars: vec!["?x".to_string()], project: Counters::new("Project"), @@ -321,14 +345,29 @@ impl Stream { Ok(Some(rows)) } - /// Stop every operator. Idempotent; dropping the stream does the same. + /// Stop every operator and release what the query holds. Idempotent; + /// dropping the stream does the same. pub(crate) fn close(&mut self) { if !self.closed { self.closed = true; self.root.close(); + // Drop the tree, which releases what every operator holds (a + // hashed body keeps its table across a close, for its next + // rewind), and keep its counters. + let mut counters = Vec::new(); + self.root.counters(&mut counters); + self.root = Box::new(Closed(counters)); + self.ids.release(); + self.relations = None; } } + /// The query's meter. + #[cfg(test)] + pub(crate) fn meter(&self) -> &Arc { + &self.meter + } + pub(crate) fn vars(&self) -> &[String] { &self.vars } @@ -353,6 +392,23 @@ impl Stream { } } +/// What is left of a closed stream's operators: their counters. +struct Closed(Vec); + +impl Operator for Closed { + fn next_batch(&mut self, _: &mut Ctx<'_>) -> Result> { + Ok(None) + } + + fn rewind(&mut self, _: &[cell::Cell]) {} + + fn close(&mut self) {} + + fn counters(&self, out: &mut Vec) { + out.extend_from_slice(&self.0); + } +} + impl Drop for Stream { fn drop(&mut self) { self.close(); diff --git a/src/query/engine/oracle.rs b/src/query/engine/oracle.rs index ab323d3e18..da264af542 100644 --- a/src/query/engine/oracle.rs +++ b/src/query/engine/oracle.rs @@ -1,12 +1,14 @@ //! The existing executor as an oracle for the engine (#473 spec §9). +use crate::error::{CodedError, ErrorCode}; use crate::query::datalog::executor::QueryResult; use crate::storage::index::encode_value; use anyhow::Result; /// Panic unless `engine` and `oracle` give the same answer: both errors, or -/// the same columns and the same rows as a bag. Messages hold counts and -/// column names only, never values. +/// the same columns and the same rows as a bag. An engine `QRY-012` agrees +/// with any answer, as the executor does not count memory (#549). Messages +/// hold counts and column names only, never values. /// /// Built only for tests (`cfg(test)`, the `test-oracle` feature), where a /// panic is how a disagreement fails the test. @@ -14,6 +16,8 @@ use anyhow::Result; pub(crate) fn check(engine: &Result, oracle: &Result) { match (engine, oracle) { (Err(_), Err(_)) => {} + (Err(e), Ok(_)) + if e.downcast_ref::().map(CodedError::code) == Some(ErrorCode::Qry012) => {} ( Ok(QueryResult::QueryResults { vars: v1, diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index cd6b37edb8..fb9b60c6c9 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -928,10 +928,16 @@ impl Builder { if let JoinKind::Hash { build_inner } = &mut join.kind { // With the test switch off, always the inner pattern // (decision 3 of the #596 plan). After a seed and no - // pattern, the seed (`branch_cost` of nothing is 0). + // pattern, the seed (both costs of nothing are 0). + // With no key, the outer side is up to the product + // of its patterns (#549 spec §6.1). + let outer = if join.keys.is_empty() { + optimizer::product_cost(&self.outer_patterns) + } else { + optimizer::branch_cost(&self.outer_patterns) + }; *build_inner = !optimizer::reorder() - || optimizer::branch_cost(&[WhereClause::Pattern(q.clone())]) - <= optimizer::branch_cost(&self.outer_patterns); + || optimizer::branch_cost(&[WhereClause::Pattern(q.clone())]) <= outer; } self.steps.push(Step::Join(join)); } diff --git a/src/query/engine/recursive.rs b/src/query/engine/recursive.rs index bc83e2319b..daa58de311 100644 --- a/src/query/engine/recursive.rs +++ b/src/query/engine/recursive.rs @@ -11,6 +11,7 @@ use super::cell::{Cell, JoinKey, Scalar}; use super::ids::IdSpace; +use super::meter::{HASH_ENTRY_OVERHEAD, Held, Meter, cell_bytes, growth, key_bytes}; use super::plan::{HeadArg, RuleRun, RulesPlan, ScanSpec, Term}; use super::relation::Relations; use super::scan::Scan; @@ -22,6 +23,8 @@ use crate::query::datalog::functions::FunctionRegistry; use crate::storage::KeySource; use anyhow::Result; use std::collections::HashSet; +use std::mem::size_of; +use std::sync::Arc; /// The limits of one rule query (spec §3.5). #[derive(Debug, Clone, Copy)] @@ -30,6 +33,8 @@ pub(crate) struct Limits { /// Facts the rules may derive in total; stored facts and magic seeds do /// not count. pub(crate) max_derived_facts: usize, + /// The most bytes the query may hold (#549). + pub(crate) query_memory: usize, } /// What every body run reads. @@ -46,11 +51,12 @@ pub(crate) fn evaluate( reads: &Reads<'_>, ids: &mut IdSpace, limits: Limits, + meter: &Arc, ) -> Result<()> { let mut derived = 0usize; for (stratum_rels, rules) in &plan.strata { for &rel in stratum_rels { - know_stored(plan, rel, rels, reads, ids)?; + know_stored(plan, rel, rels, reads, ids, meter)?; } let mut round = 0; loop { @@ -65,8 +71,12 @@ pub(crate) fn evaluate( &rule.deltas }; for run in runs { - for row in heads(run, &rule.predicate, rule.rel, rels, reads, ids)? { - if rels.add(rule.rel, row) { + let (rows, mut held) = + heads(run, &rule.predicate, rule.rel, rels, reads, ids, meter)?; + for row in rows { + // From the candidates to the relation. + held.uncharge(head_bytes(&row)); + if rels.add(rule.rel, row)? { derived += 1; if derived > limits.max_derived_facts { return Err(derived_facts_exceeded(limits.max_derived_facts)); @@ -91,6 +101,7 @@ fn know_stored( rels: &mut Relations, reads: &Reads<'_>, ids: &mut IdSpace, + meter: &Arc, ) -> Result<()> { let Some(attr) = plan.evaluated.attrs.get(rel) else { return Ok(()); @@ -105,25 +116,34 @@ fn know_stored( width: 2, derived: None, }); - let mut stored = Vec::new(); + let mut stored: Vec<(Cell, Cell)> = Vec::new(); + // The buffer of stored rows, released on return (#549 spec §3.2). + let mut held = Held::new(meter, "Recursive"); { let mut ctx = ctx(reads, ids, None); while let Some(batch) = scan.next_batch(&mut ctx)? { let (Some(es), Some(vs)) = (batch.cols.first(), batch.cols.get(1)) else { continue; }; - stored.extend(es.iter().cloned().zip(vs.iter().cloned())); + for (e, v) in es.iter().zip(vs) { + let n = cell_bytes(e) + cell_bytes(v); + held.charge(n)?; + let refused = growth(stored.capacity(), size_of::<(Cell, Cell)>()); + held.reserve(stored.try_reserve(1), n, refused)?; + stored.push((e.clone(), v.clone())); + } } } ids.end_pull(); for (e, v) in stored { - rels.know(rel, &[e, v]); + rels.know(rel, &[e, v])?; } Ok(()) } /// The heads one run of a rule's body gives that `rels` does not know yet, -/// each once. +/// each once, and what they hold on the meter until the caller drops it. +#[allow(clippy::too_many_arguments)] fn heads( run: &RuleRun, predicate: &str, @@ -131,12 +151,14 @@ fn heads( rels: &Relations, reads: &Reads<'_>, ids: &mut IdSpace, -) -> Result> { - let mut out = Vec::new(); + meter: &Arc, +) -> Result<(Vec<[Cell; 2]>, Held)> { + let mut out: Vec<[Cell; 2]> = Vec::new(); let mut seen: HashSet<[JoinKey; 2]> = HashSet::new(); + let mut held = Held::new(meter, "Recursive"); { let mut ctx = ctx(reads, ids, Some(rels)); - let mut root = build(run.plan.source.clone(), run.plan.steps.clone()); + let mut root = build(run.plan.source.clone(), run.plan.steps.clone(), meter); while let Some(batch) = root.next_batch(&mut ctx)? { for i in 0..batch.len { let cell = |slot: usize| batch.cols.get(slot).and_then(|c| c.get(i)); @@ -144,17 +166,35 @@ fn heads( entity(&run.entity, predicate, cell, &mut ctx)?, value(run.value.as_ref(), cell)?, ]; - if !rels.known(rel, &row) - && seen.insert([JoinKey::ident(&row[0]), JoinKey::ident(&row[1])]) - { - out.push(row); + if rels.known(rel, &row) { + continue; + } + let k = [JoinKey::ident(&row[0]), JoinKey::ident(&row[1])]; + if seen.contains(&k) { + continue; } + // The candidate row and its key (#549 spec §3.2). + let n = head_bytes(&row); + held.charge(n)?; + let key = key_bytes(&k[0]) + key_bytes(&k[1]) + HASH_ENTRY_OVERHEAD; + let refused = growth(seen.capacity(), key) + .saturating_add(growth(out.capacity(), size_of::<[Cell; 2]>())); + let reserved = seen.try_reserve(1).and_then(|()| out.try_reserve(1)); + held.reserve(reserved, n, refused)?; + seen.insert(k); + out.push(row); } } root.close(); } ids.end_pull(); - Ok(out) + Ok((out, held)) +} + +/// A candidate head and its key in `heads`' set. +fn head_bytes(row: &[Cell; 2]) -> usize { + let key = key_bytes(&JoinKey::ident(&row[0])) + key_bytes(&JoinKey::ident(&row[1])); + cell_bytes(&row[0]) + cell_bytes(&row[1]) + key + HASH_ENTRY_OVERHEAD } fn ctx<'a>(reads: &Reads<'a>, ids: &'a mut IdSpace, derived: Option<&'a Relations>) -> Ctx<'a> { diff --git a/src/query/engine/relation.rs b/src/query/engine/relation.rs index 41981c22d9..26f0b9b01c 100644 --- a/src/query/engine/relation.rs +++ b/src/query/engine/relation.rs @@ -8,7 +8,11 @@ //! (spec §3.2), as [`JoinKey::ident`] compares cells. use super::cell::{Cell, JoinKey}; +use super::meter::{HASH_ENTRY_OVERHEAD, Held, Meter, cell_bytes, growth, key_bytes}; +use anyhow::Result; use std::collections::{HashMap, HashSet}; +use std::mem::size_of; +use std::sync::Arc; /// Which rows of a relation a scan reads (spec §5.2). #[derive(Debug, Clone, Copy, PartialEq, Eq)] @@ -31,6 +35,8 @@ pub(crate) struct Derived { pub(crate) struct Relations { rels: Vec, + /// Derived rows and the stored facts' keys (#549 spec §3.2). + held: Held, } struct Rel { @@ -48,8 +54,8 @@ struct Rel { } impl Relations { - /// Empty relations, one per attribute id in `iids`. - pub(crate) fn new(iids: impl IntoIterator) -> Self { + /// Empty relations, one per attribute id in `iids`, counting on `meter`. + pub(crate) fn new(iids: impl IntoIterator, meter: &Arc) -> Self { Relations { rels: iids .into_iter() @@ -63,6 +69,7 @@ impl Relations { end: 0, }) .collect(), + held: Held::new(meter, "Relations"), } } @@ -72,10 +79,20 @@ impl Relations { } /// Record a stored fact of relation `rel`: a row equal to it is not new. - pub(crate) fn know(&mut self, rel: usize, row: &[Cell; 2]) { - if let Some(r) = self.rels.get_mut(rel) { - r.ident.insert(key(row)); + pub(crate) fn know(&mut self, rel: usize, row: &[Cell; 2]) -> Result<()> { + let Some(r) = self.rels.get_mut(rel) else { + return Ok(()); + }; + let k = key(row); + if r.ident.contains(&k) { + return Ok(()); } + let n = ident_bytes(&k); + self.held.charge(n)?; + let refused = growth(r.ident.capacity(), n); + self.held.reserve(r.ident.try_reserve(1), n, refused)?; + r.ident.insert(k); + Ok(()) } /// Whether `row` is already a stored fact or a row of `rel`, this @@ -88,15 +105,49 @@ impl Relations { /// Add `row` to `rel` at the end of the round, unless it is known. /// Returns whether it was new. - pub(crate) fn add(&mut self, rel: usize, row: [Cell; 2]) -> bool { + pub(crate) fn add(&mut self, rel: usize, row: [Cell; 2]) -> Result { let Some(r) = self.rels.get_mut(rel) else { - return false; + return Ok(false); + }; + let k = key(&row); + if r.ident.contains(&k) { + return Ok(false); + } + // The row in `next` then `rows`, its key, its entity slot, and a + // new entity's entry in `by_entity`. + let entity = match row[0] { + Cell::Eid(e) => Some(e), + _ => None, }; - if !r.ident.insert(key(&row)) { - return false; + let new_entity = entity.is_some_and(|e| !r.by_entity.contains_key(&e)); + let entry = size_of::() + size_of::>() + HASH_ENTRY_OVERHEAD; + let cells = cell_bytes(&row[0]) + cell_bytes(&row[1]); + let n = + 2 * cells + ident_bytes(&k) + size_of::() + if new_entity { entry } else { 0 }; + self.held.charge(n)?; + let refused = growth(r.ident.capacity(), ident_bytes(&k)) + .saturating_add(growth(r.next.capacity(), cells)) + .saturating_add(growth(r.rows.capacity(), cells)) + .saturating_add(growth(r.by_entity.capacity(), entry)); + let reserved = r + .ident + .try_reserve(1) + .and_then(|()| r.next.try_reserve(1)) + .and_then(|()| r.rows.try_reserve(r.next.len() + 1)) + .and_then(|()| r.by_entity.try_reserve(1)); + self.held.reserve(reserved, n, refused)?; + if let Some(e) = entity { + // The row's position once the round ends; until then `row` + // returns `None` for it. + let at = r.rows.len() + r.next.len(); + let slots = r.by_entity.entry(e).or_default(); + let refused = growth(slots.capacity(), size_of::()); + self.held.reserve(slots.try_reserve(1), n, refused)?; + slots.push(at); } + r.ident.insert(k); r.next.push(row); - true + Ok(true) } /// End a round: append every relation's new rows, which become the @@ -106,12 +157,8 @@ impl Relations { for r in &mut self.rels { r.start = r.end; any |= !r.next.is_empty(); - for row in r.next.drain(..) { - if let Cell::Eid(e) = row[0] { - r.by_entity.entry(e).or_default().push(r.rows.len()); - } - r.rows.push(row); - } + // `rows` has room: `add` reserved it, and indexed each entity. + r.rows.append(&mut r.next); r.end = r.rows.len(); } any @@ -129,7 +176,8 @@ impl Relations { } } - /// The positions of `rel`'s rows whose entity is `eid`, in any range. + /// The positions of `rel`'s rows whose entity is `eid`, in any range, + /// and those of the round under way, which `row` does not return yet. pub(crate) fn of_entity(&self, rel: usize, eid: u64) -> &[usize] { self.rels .get(rel) @@ -152,6 +200,11 @@ fn key(row: &[Cell; 2]) -> [JoinKey; 2] { [JoinKey::ident(&row[0]), JoinKey::ident(&row[1])] } +/// An identity key in a hash set. +fn ident_bytes(k: &[JoinKey; 2]) -> usize { + key_bytes(&k[0]) + key_bytes(&k[1]) + HASH_ENTRY_OVERHEAD +} + #[cfg(test)] mod tests { use super::*; @@ -165,29 +218,44 @@ mod tests { /// keyword distinct from the entity it names. #[test] fn identity_of_rows() { - let mut r = Relations::new([7]); - assert!(r.add(0, row(1, Scalar::Float(0.0)))); - assert!(r.add(0, row(1, Scalar::Float(-0.0))), "-0.0 is new"); - assert!(!r.add(0, row(1, Scalar::Float(0.0))), "0.0 again"); - assert!(r.add(0, row(1, Scalar::Float(f64::NAN)))); - assert!(!r.add(0, row(1, Scalar::Float(-f64::NAN))), "one NaN"); - assert!(r.add(0, row(1, Scalar::Int(0))), "integer is not float"); - assert!(r.add(0, [Cell::Eid(1), Cell::Iid(5)])); - assert!(r.add(0, [Cell::Eid(1), Cell::Eid(5)]), "ref is not keyword"); - r.know(0, &row(2, Scalar::Bool(true))); - assert!(!r.add(0, row(2, Scalar::Bool(true))), "stored fact"); + let mut r = Relations::new([7], &Meter::unlimited()); + assert!(r.add(0, row(1, Scalar::Float(0.0))).unwrap()); + assert!( + r.add(0, row(1, Scalar::Float(-0.0))).unwrap(), + "-0.0 is new" + ); + assert!(!r.add(0, row(1, Scalar::Float(0.0))).unwrap(), "0.0 again"); + assert!(r.add(0, row(1, Scalar::Float(f64::NAN))).unwrap()); + assert!( + !r.add(0, row(1, Scalar::Float(-f64::NAN))).unwrap(), + "one NaN" + ); + assert!( + r.add(0, row(1, Scalar::Int(0))).unwrap(), + "integer is not float" + ); + assert!(r.add(0, [Cell::Eid(1), Cell::Iid(5)]).unwrap()); + assert!( + r.add(0, [Cell::Eid(1), Cell::Eid(5)]).unwrap(), + "ref is not keyword" + ); + r.know(0, &row(2, Scalar::Bool(true))).unwrap(); + assert!( + !r.add(0, row(2, Scalar::Bool(true))).unwrap(), + "stored fact" + ); assert!(r.known(0, &row(1, Scalar::Int(0)))); } #[test] fn rounds_give_old_delta_and_full() { - let mut r = Relations::new([7]); - r.add(0, row(1, Scalar::Int(1))); + let mut r = Relations::new([7], &Meter::unlimited()); + r.add(0, row(1, Scalar::Int(1))).unwrap(); assert_eq!(r.span(0, Range::Full), 0..0, "not before the round ends"); assert!(r.end_round()); assert_eq!(r.span(0, Range::Delta), 0..1); - r.add(0, row(1, Scalar::Int(2))); - r.add(0, row(2, Scalar::Int(3))); + r.add(0, row(1, Scalar::Int(2))).unwrap(); + r.add(0, row(2, Scalar::Int(3))).unwrap(); assert!(r.end_round()); assert_eq!(r.span(0, Range::Old), 0..1); assert_eq!(r.span(0, Range::Delta), 1..3); diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 8823496bd6..bc978cca0a 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -1852,3 +1852,342 @@ fn rule_queries_read_derived_rows_in_batches() { db.checkpoint().unwrap(); } } + +// ── #549: query memory accounting ────────────────────────────────────────── + +/// A checkpointed database of `n` entities, each with integers `:a` and +/// `:b`, both its number. Queries over variable attributes +/// read ids straight from keys, so their first holder is an operator rather +/// than the query's `IdSpace`. +fn memory_db(dir: &std::path::Path, n: usize, limit: usize) -> Minigraf { + let path = dir.join("memory.graph"); + { + let db = Minigraf::open(&path).unwrap(); + let facts: String = (0..n) + .map(|i| format!("[:p{i} :a {i}] [:p{i} :b {i}]")) + .collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + db.checkpoint().unwrap(); + } + crate::OpenOptions::new() + .query_memory_limit(limit) + .path(&path) + .open() + .unwrap() +} + +/// One shape per operator that holds state, the operator that holds it +/// first, and the entities its database needs: more than one batch of +/// answer rows, few enough that the executor oracle's cross joins stay fast. +const MEMORY_SHAPES: [(&str, usize, &str); 5] = [ + ( + "HashJoin", + 300, + "(query [:find ?e :where [?e ?a ?x] [?f ?b ?x]])", + ), + ( + "AntiJoin", + 300, + "(query [:find ?e :where [?e ?a ?x] (not-join [?x] [?f ?b ?x] [(< ?x 100)])])", + ), + ( + "Union", + 300, + "(query [:find ?e ?f :where [?e ?a ?x] \ + (or (and [?f ?b ?x] [(> ?x 5)]) (and [?f ?b ?x] [(< ?x 9)]))])", + ), + ( + "Aggregate", + 1100, + "(query [:find ?x (count ?e) :where [?e ?a ?x]])", + ), + ( + "Window", + 1100, + "(query [:find ?e (rank :over (:order-by ?x)) :where [?e ?a ?x]])", + ), +]; + +/// Every holder charges while it holds state, and the meter is back at 0 +/// once the stream is drained or dropped early (#549 spec §6.2). +#[test] +fn holders_charge_and_the_meter_returns_to_zero() { + for (op, n, query) in MEMORY_SHAPES { + let dir = tempfile::tempdir().unwrap(); + let db = memory_db(dir.path(), n, usize::MAX); + let mut cursor = db.query(query).unwrap(); + let meter = cursor.stream_mut().expect("engine").meter().clone(); + assert!(cursor.next_batch(1).unwrap().is_some(), "{op}: a row"); + assert!(meter.peak() > 0, "{op}: charged"); + if op != "Union" { + let held = cursor + .stream_mut() + .expect("engine") + .counters() + .iter() + .filter(|c| c.op == op) + .map(|c| c.bytes_held) + .sum::(); + assert!(held > 0, "{op}: holds state between pulls"); + } + while cursor.next_batch(4096).unwrap().is_some() {} + assert_eq!(meter.used(), 0, "{op}: drained"); + + let mut cursor = db.query(query).unwrap(); + let meter = cursor.stream_mut().expect("engine").meter().clone(); + cursor.next_batch(1).unwrap(); + drop(cursor); + assert_eq!(meter.used(), 0, "{op}: dropped early"); + } +} + +/// The holder that would go over the limit is named (#549 spec §4). +#[test] +fn qry_012_names_the_holder_over_the_limit() { + for (op, n, query) in MEMORY_SHAPES { + let dir = tempfile::tempdir().unwrap(); + let db = memory_db(dir.path(), n, 1); + let err = db.execute(query).expect_err(op); + assert_eq!(err.code(), "QRY-012", "{op}"); + let text = err.to_string(); + assert!(text.contains(&format!("{op} needs")), "{op}: {text}"); + assert!(text.contains("of its 1-byte limit"), "{op}: {text}"); + } + + // Pending entities take provisional ids. + let db = crate::OpenOptions::new() + .query_memory_limit(1) + .open_memory() + .unwrap(); + db.execute("(transact [[:x :a 1]])").unwrap(); + let err = db + .execute("(query [:find ?e :where [?e :a ?v]])") + .expect_err("ids"); + assert!(err.to_string().contains("IdSpace needs"), "IdSpace"); + + // A rule query's candidate heads: enough for its ids, not its rows. + let dir = tempfile::tempdir().unwrap(); + let db = memory_db(dir.path(), 300, 2000); + db.execute("(rule [(r ?x ?y) [?x :a ?y]])").unwrap(); + let err = db + .execute("(query [:find ?x ?y :where (r ?x ?y)])") + .expect_err("rules"); + assert_eq!(err.code(), "QRY-012"); + assert!(err.to_string().contains("Recursive needs"), "Recursive"); +} + +/// A refused allocation is `QRY-012` naming the holder (spec §4, second +/// form), through the test hook. +#[test] +fn qry_012_allocator_form() { + let dir = tempfile::tempdir().unwrap(); + let db = memory_db(dir.path(), 300, usize::MAX); + for (op, _, query) in MEMORY_SHAPES { + super::meter::FAIL_RESERVE.with(|f| f.set(Some(op))); + let err = db.execute(query).expect_err(op); + super::meter::FAIL_RESERVE.with(|f| f.set(None)); + assert_eq!(err.code(), "QRY-012", "{op}"); + let text = err.to_string(); + assert!( + text.contains("the allocator refused") && text.ends_with(&format!("bytes for {op}")), + "{op}: {text}" + ); + db.execute(query).expect("the next query runs"); + } +} + +/// A cursor that returned rows and then reaches the limit gives the error +/// on the next call; the database then answers other queries. +#[test] +fn cursor_returns_rows_then_qry_012() { + let db = crate::OpenOptions::new() + .query_memory_limit(120_000) + .open_memory() + .unwrap(); + let facts: String = (0..3000).map(|i| format!("[:p{i} :a {i}]")).collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + // Each new pending entity takes a provisional id, held to the end. + let mut cursor = db.query("(query [:find ?e :where [?e :a ?v]])").unwrap(); + let mut rows = 0; + let err = loop { + match cursor.next_batch(1024) { + Ok(Some(batch)) => rows += batch.len(), + Ok(None) => panic!("expected QRY-012"), + Err(e) => break e, + } + }; + assert!(rows >= 1024, "rows before the error"); + assert_eq!(err.code(), "QRY-012"); + assert!(cursor.next_batch(1024).unwrap().is_none(), "then done"); + let QueryResult::QueryResults { results, .. } = + db.execute("(query [:find ?v :where [:p1 :a ?v]])").unwrap() + else { + panic!("expected query results"); + }; + assert_eq!(results.len(), 1, "the database answers"); +} + +/// Integers `0..n` in slot 0, in batches. +struct Ints { + n: i64, + at: i64, +} + +impl super::Operator for Ints { + fn next_batch(&mut self, _: &mut super::Ctx<'_>) -> anyhow::Result> { + if self.at >= self.n { + return Ok(None); + } + let mut batch = super::Batch::new(1); + while batch.len < super::BATCH_ROWS && self.at < self.n { + batch.push(&mut [Some(super::cell::Cell::Val(super::cell::Scalar::Int( + self.at, + )))]); + self.at += 1; + } + Ok(Some(batch)) + } + + fn rewind(&mut self, _: &[super::cell::Cell]) { + self.at = 0; + } + + fn close(&mut self) { + self.at = self.n; + } + + fn counters(&self, _: &mut Vec) {} +} + +/// Pull `op` once with a fresh context over `meter`. +fn pull_once( + op: &mut dyn super::Operator, + meter: &std::sync::Arc, +) -> anyhow::Result> { + let snapshot = crate::graph::storage::FactStorage::new() + .snapshot() + .unwrap(); + let functions = crate::query::datalog::functions::FunctionRegistry::with_builtins(); + let mut ids = super::ids::IdSpace::new(None, meter); + let mut ctx = super::Ctx { + snapshot: &snapshot, + keys: None, + ids: &mut ids, + functions: &functions, + derived: None, + }; + op.next_batch(&mut ctx) +} + +/// `rewind` and `close` release what an operator holds (spec §3.1). +#[test] +fn rewind_and_close_release() { + let meter = super::Meter::unlimited(); + let ints = || Box::new(Ints { n: 3000, at: 0 }); + let mut distinct = super::distinct::Distinct::new(ints(), vec![0], &meter); + let mut aggregate = super::aggregate::Aggregate::new( + ints(), + vec![0], + vec![("count".to_string(), 0)], + false, + &meter, + ); + let ops: [&mut dyn super::Operator; 2] = [&mut distinct, &mut aggregate]; + for op in ops { + pull_once(op, &meter).unwrap().expect("a batch"); + assert!(meter.used() > 0, "held after a pull"); + op.rewind(&[]); + assert_eq!(meter.used(), 0, "released by rewind"); + pull_once(op, &meter).unwrap().expect("a batch"); + assert!(meter.used() > 0, "held again"); + op.close(); + assert_eq!(meter.used(), 0, "released by close"); + } +} + +/// Each operator over a small limit names itself; a rule query's relation +/// too. +#[test] +fn small_limit_in_each_holder() { + let meter = super::Meter::new(100); + let mut distinct = + super::distinct::Distinct::new(Box::new(Ints { n: 10, at: 0 }), vec![0], &meter); + let err = pull_once(&mut distinct, &meter).unwrap_err(); + assert!(err.to_string().contains("Distinct needs"), "Distinct"); + super::Operator::close(&mut distinct); + assert_eq!(meter.used(), 0, "nothing counted after the error and close"); + + let mut aggregate = super::aggregate::Aggregate::new( + Box::new(Ints { n: 10, at: 0 }), + vec![0], + vec![("count".to_string(), 0)], + false, + &meter, + ); + let err = pull_once(&mut aggregate, &meter).unwrap_err(); + assert!(err.to_string().contains("Aggregate needs"), "Aggregate"); + + let meter = super::Meter::new(300); + let mut rels = super::relation::Relations::new([7], &meter); + let row = |n| { + [ + super::cell::Cell::Eid(n), + super::cell::Cell::Val(super::cell::Scalar::Int(1)), + ] + }; + rels.add(0, row(1)).unwrap(); + let err = (2..10) + .find_map(|n| rels.add(0, row(n)).err()) + .expect("limit"); + assert!(err.to_string().contains("Relations needs"), "Relations"); + assert!(meter.used() > 0); + drop(rels); + assert_eq!(meter.used(), 0, "released on drop"); +} + +/// A join with no key builds on its inner pattern unless the outer side's +/// product estimate is smaller (#549 spec §6.1). +#[test] +fn planner_builds_a_keyless_join_on_the_smaller_product() { + use super::plan::{JoinKind, Step, plan}; + use crate::query::datalog::parser::parse_datalog_command; + use crate::query::datalog::types::DatalogCommand; + let sides = |q: &str| -> Vec { + let Ok(DatalogCommand::Query(query)) = parse_datalog_command(q) else { + panic!("expected a query"); + }; + plan(&query) + .expect("an engine plan") + .steps + .iter() + .filter_map(|s| match s { + Step::Join(j) => match j.kind { + JoinKind::Hash { build_inner } => Some(build_inner), + JoinKind::Probe(_) => None, + }, + _ => None, + }) + .collect() + }; + // #575: the outer side is 100 rows, then at least 100 × 10,000. + assert_eq!( + sides("(query [:find ?n :where [?e0 :n ?n] [?e1 ?a1 ?v1] [?e2 ?a2 ?v2] [?e3 ?a3 ?v3]])"), + [false, true, true] + ); + assert_eq!( + sides("(query [:find ?e :where [?e :name \"x\"] [?p ?q ?r]])"), + [false], + "a selective outer side" + ); + assert_eq!( + sides("(query [:find ?e :where [?e :a ?x] [?f :b ?y]])"), + [true], + "a tie builds inner" + ); + let _off = crate::query::datalog::optimizer::set_reorder(false); + assert_eq!( + sides("(query [:find ?n :where [?e0 :n ?n] [?e1 ?a1 ?v1] [?e2 ?a2 ?v2]])"), + [true, true], + "reorder off builds inner" + ); +} diff --git a/src/query/engine/union.rs b/src/query/engine/union.rs index 1d6e4dbefe..c83a95696a 100644 --- a/src/query/engine/union.rs +++ b/src/query/engine/union.rs @@ -13,10 +13,13 @@ use super::batch::Batch; use super::cell::{Cell, JoinKey}; +use super::meter::{HASH_ENTRY_OVERHEAD, Held, Meter, growth, keys_bytes, row_bytes}; use super::plan::{Body as Spec, Branch, Key}; use super::{BATCH_ROWS, Counters, Ctx, Operator, build}; use anyhow::Result; use std::collections::HashMap; +use std::mem::size_of; +use std::sync::Arc; pub(crate) struct Union { outer: Box, @@ -25,6 +28,11 @@ pub(crate) struct Union { width: usize, /// The outer batch being extended. at: Option, + /// The hashed branches' tables (#549 spec §3.2), counted as long as + /// they are kept: until the operator drops. + tables: Held, + /// `At.rows`, released as they are returned. + buffered: Held, /// `rows_in` counts the outer rows received. counters: Counters, } @@ -62,19 +70,19 @@ enum Body { } impl Union { - pub(crate) fn new(outer: Box, branches: Vec) -> Self { + pub(crate) fn new(outer: Box, branches: Vec, meter: &Arc) -> Self { let width = branches.first().map_or(0, |b| b.new.len()); let arms = branches .into_iter() .map(|Branch { body, new }| Arm { body: match body { Spec::Correlated { plan, imports } => Body::Correlated { - root: build(plan.source, plan.steps), + root: build(plan.source, plan.steps, meter), imports, seed: Vec::new(), }, Spec::Hashed { plan, keys } => Body::Hashed { - root: build(plan.source, plan.steps), + root: build(plan.source, plan.steps, meter), keys, table: None, }, @@ -87,6 +95,8 @@ impl Union { arms, width, at: None, + tables: Held::new(meter, "Union"), + buffered: Held::new(meter, "Union"), counters: Counters::new("Union"), } } @@ -99,13 +109,17 @@ fn cell(batch: &Batch, slot: usize, i: usize) -> Option<&Cell> { impl Arm { /// Append the new cells of the branch's rows for row `i` of `batch` to - /// `out`; with `one`, at most one row. + /// `out`, counted on `buffered`; with `one`, at most one row. A hashed + /// branch's table is counted on `tables`. + #[allow(clippy::too_many_arguments)] fn rows( &mut self, batch: &Batch, i: usize, one: bool, out: &mut Vec>, + tables: &mut Held, + buffered: &mut Held, ctx: &mut Ctx<'_>, ) -> Result<()> { let new = &self.new; @@ -125,11 +139,13 @@ impl Arm { root.rewind(seed); 'pull: while let Some(b) = root.next_batch(ctx)? { for j in 0..b.len { - out.push( + buffer( + out, new.iter() .filter_map(|&s| cell(&b, s, j).cloned()) .collect(), - ); + buffered, + )?; if one { break 'pull; } @@ -139,7 +155,7 @@ impl Arm { } Body::Hashed { root, keys, table } => { if table.is_none() { - *table = Some(collect(root.as_mut(), keys, new, one, ctx)?); + *table = Some(collect(root.as_mut(), keys, new, one, tables, ctx)?); } let Some(table) = table else { return Ok(()); @@ -156,9 +172,12 @@ impl Arm { key.push(j); } if let Some(rows) = table.get(&key) { - match rows.first() { - Some(r) if one => out.push(r.clone()), - _ => out.extend(rows.iter().cloned()), + let rows = match rows.first() { + Some(first) if one => std::slice::from_ref(first), + _ => rows.as_slice(), + }; + for r in rows { + buffer(out, r.clone(), buffered)?; } } } @@ -179,13 +198,24 @@ impl Arm { } } +/// Append `row` to `out`, counted on `held`. +fn buffer(out: &mut Vec>, row: Vec, held: &mut Held) -> Result<()> { + let n = row_bytes(&row); + held.charge(n)?; + let refused = growth(out.capacity(), size_of::>()); + held.reserve(out.try_reserve(1), n, refused)?; + out.push(row); + Ok(()) +} + /// Every row of a hashed branch: its new cells by the keys of `keys`' inner -/// slots. With `one`, one row per key. +/// slots, counted on `held`. With `one`, one row per key. fn collect( root: &mut dyn Operator, keys: &[Key], new: &[usize], one: bool, + held: &mut Held, ctx: &mut Ctx<'_>, ) -> Result, Vec>>> { let mut table: HashMap, Vec>> = HashMap::new(); @@ -202,14 +232,26 @@ fn collect( }; key.push(j); } - let rows = table.entry(key).or_default(); - if !one || rows.is_empty() { - rows.push( - new.iter() - .filter_map(|&s| cell(&b, s, i).cloned()) - .collect(), - ); + let found = table.contains_key(&key); + if one && found { + continue; } + let row: Vec = new + .iter() + .filter_map(|&s| cell(&b, s, i).cloned()) + .collect(); + // A new key's entry: the key and its rows' header; then the row. + let entry = keys_bytes(&key) + size_of::>>() + HASH_ENTRY_OVERHEAD; + let n = row_bytes(&row) + if found { 0 } else { entry }; + held.charge(n)?; + if !found { + let refused = growth(table.capacity(), entry); + held.reserve(table.try_reserve(1), n, refused)?; + } + let rows = table.entry(key).or_default(); + let refused = growth(rows.capacity(), size_of::>()); + held.reserve(rows.try_reserve(1), n, refused)?; + rows.push(row); } } root.close(); @@ -239,6 +281,9 @@ impl Operator for Union { }; let out = out.get_or_insert_with(|| Batch::new(at.batch.cols.len() + self.width)); while at.done < at.rows.len() && out.len < BATCH_ROWS { + if let Some(new) = at.rows.get(at.done) { + self.buffered.uncharge(row_bytes(new)); + } let mut row: Vec> = at .batch .cols @@ -262,8 +307,17 @@ impl Operator for Union { at.next += 1; at.rows.clear(); at.done = 0; + self.buffered.release(); for arm in &mut self.arms { - arm.rows(&at.batch, at.row, one, &mut at.rows, ctx)?; + arm.rows( + &at.batch, + at.row, + one, + &mut at.rows, + &mut self.tables, + &mut self.buffered, + ctx, + )?; if one && !at.rows.is_empty() { break; } @@ -280,11 +334,13 @@ impl Operator for Union { fn rewind(&mut self, seed: &[Cell]) { self.at = None; + self.buffered.release(); self.outer.rewind(seed); } fn close(&mut self) { self.at = None; + self.buffered.release(); self.outer.close(); for arm in &mut self.arms { arm.root_mut().close(); @@ -292,7 +348,10 @@ impl Operator for Union { } fn counters(&self, out: &mut Vec) { - out.push(self.counters); + out.push(Counters { + bytes_held: (self.tables.bytes() + self.buffered.bytes()) as u64, + ..self.counters + }); for arm in &self.arms { arm.root().counters(out); } diff --git a/src/query/engine/window.rs b/src/query/engine/window.rs index fa91192166..7783a7c71c 100644 --- a/src/query/engine/window.rs +++ b/src/query/engine/window.rs @@ -10,12 +10,15 @@ use super::batch::Batch; use super::cell::{Cell, Scalar}; +use super::meter::{Held, Meter, cell_bytes, growth, row_bytes, value_bytes}; use super::project::value; use super::{BATCH_ROWS, Counters, Ctx, Operator}; use crate::graph::types::Value; use crate::query::datalog::aggregate::windows; use crate::query::datalog::types::FindSpec; use anyhow::Result; +use std::mem::size_of; +use std::sync::Arc; pub(crate) struct Window { child: Box, @@ -30,6 +33,11 @@ pub(crate) struct Window { values: Vec>, /// The finished rows, last first, once the input has ended. out: Option>>, + /// `cells`, then the finished rows, released as they are returned + /// (#549 spec §3.2). + held: Held, + /// `values`, until the windows are computed. + held_values: Held, counters: Counters, } @@ -39,6 +47,7 @@ impl Window { find: Vec, named: Vec, keep: Vec, + meter: &Arc, ) -> Self { Window { child, @@ -48,6 +57,8 @@ impl Window { cells: Vec::new(), values: Vec::new(), out: None, + held: Held::new(meter, "Window"), + held_values: Held::new(meter, "Window"), counters: Counters::new("Window"), } } @@ -60,14 +71,23 @@ impl Window { let cell = |slot: usize, i: usize| batch.cols.get(slot).and_then(|c| c.get(i)).unwrap_or(&null); for i in 0..batch.len { - self.cells - .push(self.keep.iter().map(|&s| cell(s, i).clone()).collect()); - self.values.push( - self.named - .iter() - .map(|&s| value(cell(s, i), ctx)) - .collect::>>()?, - ); + let cells: Vec = self.keep.iter().map(|&s| cell(s, i).clone()).collect(); + let n = row_bytes(&cells); + self.held.charge(n)?; + let refused = growth(self.cells.capacity(), size_of::>()); + self.held.reserve(self.cells.try_reserve(1), n, refused)?; + let values = self + .named + .iter() + .map(|&s| value(cell(s, i), ctx)) + .collect::>>()?; + let v = size_of::>() + values.iter().map(value_bytes).sum::(); + self.held_values.charge(v)?; + let refused = growth(self.values.capacity(), size_of::>()); + self.held_values + .reserve(self.values.try_reserve(1), v, refused)?; + self.cells.push(cells); + self.values.push(values); } Ok(()) } @@ -76,9 +96,17 @@ impl Window { fn finish(&mut self, ctx: &mut Ctx<'_>) -> Result>> { let values = std::mem::take(&mut self.values); let mut rows = std::mem::take(&mut self.cells); - for column in windows(&self.find, &values, ctx.functions)? { + let columns = windows(&self.find, &values, ctx.functions)?; + drop(values); + self.held_values.release(); + for column in columns { for (row, v) in rows.iter_mut().zip(&column) { - row.push(Cell::of_value(ctx.ids, ctx.keys, v)?); + let c = Cell::of_value(ctx.ids, ctx.keys, v)?; + let n = cell_bytes(&c); + self.held.charge(n)?; + let refused = growth(row.capacity(), size_of::()); + self.held.reserve(row.try_reserve(1), n, refused)?; + row.push(c); } } rows.reverse(); @@ -108,6 +136,7 @@ impl Operator for Window { while batch.len < BATCH_ROWS && let Some(row) = rows.pop() { + self.held.uncharge(row_bytes(&row)); batch.push(&mut row.into_iter().map(Some).collect::>()); } self.counters.out(&batch); @@ -118,6 +147,8 @@ impl Operator for Window { self.cells.clear(); self.values.clear(); self.out = None; + self.held.release(); + self.held_values.release(); self.child.rewind(seed); } @@ -125,11 +156,16 @@ impl Operator for Window { self.cells = Vec::new(); self.values = Vec::new(); self.out = Some(Vec::new()); + self.held.release(); + self.held_values.release(); self.child.close(); } fn counters(&self, out: &mut Vec) { - out.push(self.counters); + out.push(Counters { + bytes_held: (self.held.bytes() + self.held_values.bytes()) as u64, + ..self.counters + }); self.child.counters(out); } } diff --git a/tests/memory_limit_test.rs b/tests/memory_limit_test.rs new file mode 100644 index 0000000000..7f6733aa63 --- /dev/null +++ b/tests/memory_limit_test.rs @@ -0,0 +1,150 @@ +//! `OpenOptions::query_memory_limit` and `QRY-012` through the public API +//! (#549): the default, the builder, and every way a query runs. + +use minigraf::{BindValue, Minigraf, OpenOptions, QueryResult, Value}; + +/// An in-memory database with `limit`, holding 50 people. +fn db(limit: usize) -> Minigraf { + let db = OpenOptions::new() + .query_memory_limit(limit) + .open_memory() + .unwrap(); + let facts: String = (0..50) + .map(|i| format!("[:p{i} :age {i}] [:p{i} :friend :p{}]", (i + 1) % 50)) + .collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + db +} + +fn rows(result: QueryResult) -> usize { + match result { + QueryResult::QueryResults { results, .. } => results.len(), + _ => panic!("expected query results"), + } +} + +const QUERY: &str = "(query [:find ?e ?a :where [?e :age ?a]])"; + +#[test] +fn off_by_default() { + assert_eq!(OpenOptions::default().query_memory_limit, usize::MAX); + assert_eq!( + OpenOptions::new().query_memory_limit(64).query_memory_limit, + 64 + ); + let db = db(usize::MAX); + assert_eq!(rows(db.execute(QUERY).unwrap()), 50); +} + +#[test] +fn execute_and_query_fail_with_qry_012() { + let db = db(0); + let err = db.execute(QUERY).expect_err("execute"); + assert_eq!(err.code(), "QRY-012"); + assert!( + err.to_string().contains("query memory limit exceeded"), + "message" + ); + let mut cursor = db.query(QUERY).expect("a cursor opens"); + let err = cursor.next_batch(10).expect_err("the first pull"); + assert_eq!(err.code(), "QRY-012"); + assert!(cursor.next_batch(10).unwrap().is_none(), "then done"); +} + +#[test] +fn prepared_queries_are_limited() { + let db = db(0); + let prepared = db + .prepare("(query [:find ?e :where [?e :age $age]])") + .unwrap(); + let err = prepared + .execute(&[("age", BindValue::Val(Value::Integer(7)))]) + .expect_err("prepared"); + assert_eq!(err.code(), "QRY-012"); + + let db = self::db(usize::MAX); + let prepared = db + .prepare("(query [:find ?e :where [?e :age $age]])") + .unwrap(); + let result = prepared + .execute(&[("age", BindValue::Val(Value::Integer(7)))]) + .unwrap(); + assert_eq!(rows(result), 1); +} + +#[test] +fn rule_queries_are_limited() { + let rules = [ + "(rule [(reach ?x ?y) [?x :friend ?y]])", + "(rule [(reach ?x ?z) (reach ?x ?y) [?y :friend ?z]])", + ]; + let query = "(query [:find ?x ?y :where (reach ?x ?y)])"; + let db = db(10_000); + for r in rules { + db.execute(r).unwrap(); + } + let err = db.execute(query).expect_err("2,500 derived facts"); + assert_eq!(err.code(), "QRY-012"); + let err = db + .query(query) + .expect_err("rules run when the cursor opens"); + assert_eq!(err.code(), "QRY-012"); + + let db = self::db(usize::MAX); + for r in rules { + db.execute(r).unwrap(); + } + assert_eq!(rows(db.execute(query).unwrap()), 2500); +} + +#[test] +fn the_database_answers_after_qry_012() { + let db = db(4_000); + let err = db + .execute("(query [:find ?a (count ?e) :where [?e :age ?a]])") + .expect_err("50 groups"); + assert_eq!(err.code(), "QRY-012"); + let result = db + .execute("(query [:find ?a :where [:p3 :age ?a]])") + .unwrap(); + 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. +#[test] +fn write_transactions_with_staged_writes_are_not_counted_yet() { + let db = db(0); + let mut tx = db.begin_write().unwrap(); + assert_eq!( + tx.execute(QUERY).expect_err("no write yet").code(), + "QRY-012" + ); + tx.execute("(transact [[:p50 :age 50]])").unwrap(); + assert_eq!(rows(tx.execute(QUERY).unwrap()), 51); + tx.rollback(); +} + +/// A prepared rule query runs with the database's `max_derived_facts`, as +/// every other query does. +#[test] +fn prepared_rule_queries_use_the_database_limits() { + let db = OpenOptions::new() + .max_derived_facts(5) + .open_memory() + .unwrap(); + db.execute("(transact [[:a :friend :b] [:b :friend :c] [:c :friend :d] [:d :friend :e]])") + .unwrap(); + db.execute("(rule [(reach ?x ?y) [?x :friend ?y]])") + .unwrap(); + db.execute("(rule [(reach ?x ?z) (reach ?x ?y) [?y :friend ?z]])") + .unwrap(); + let prepared = db + .prepare("(query [:find ?x ?y :where (reach ?x ?y) [?y :friend $z]])") + .unwrap(); + let err = prepared + .execute(&[("z", BindValue::Val(Value::Keyword(":e".to_string())))]) + .expect_err("10 derived facts"); + assert_eq!(err.code(), "INT-020"); +}