diff --git a/.github/workflows/binary-size.yml b/.github/workflows/binary-size.yml index 699f4fa705..6ab5bb25cb 100644 --- a/.github/workflows/binary-size.yml +++ b/.github/workflows/binary-size.yml @@ -14,7 +14,7 @@ jobs: name: Check release binary size runs-on: ubuntu-latest env: - SIZE_LIMIT_BYTES: 1228800 # 1200 KiB — raised from 1 MiB for #277's structured error codes; see PHILOSOPHY.md §4 + SIZE_LIMIT_BYTES: 1259520 # 1230 KiB — raised from 1 MiB for #277's structured error codes, from 1200 KiB for #306's :order-by/top-k; see PHILOSOPHY.md §4 steps: - name: Checkout code uses: actions/checkout@v4 diff --git a/CHANGELOG.md b/CHANGELOG.md index 8d3d80d32c..672c284ee4 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -52,7 +52,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Added - **Fallible and re-entrant user functions** (#180, PR 1). `Minigraf::try_register_predicate` and `Minigraf::try_register_aggregate` take closures that return `Result<_, UdfError>` (`UdfError` is exported at the crate root). A call that returns `Err` fails the query with the new `QRY-014`, ``user function `` failed: ``, at the first failing call: it is never read as `false` or `nil`, and no later call of any user function is made for that query. `execute` and `PreparedQuery::execute` return it; a cursor treats it as any other read error, returning the rows of the batches finished before the failure, then the error, then `None`. `register_predicate` and `register_aggregate` are unchanged. A query now reads its functions from a snapshot of the registry taken when it opens, and holds no database lock while a user function runs: a function registered later is not seen by a query or cursor that is already open, and a user function may call back into its own database (query, prepare, read the fact log, write, define rules, register functions, checkpoint, verify, rebuild indexes). Its writes are not seen by the query that called it. Inside a `WriteTransaction` those calls return `INT-001` on that thread, except registration, which runs. Before, a user function that registered a function deadlocked. This is the core of UDF registration in the language bindings, which follows binding by binding. -- **`:limit N` bounds the rows a query returns** (#306, PR 1 of 2). `[:find … :where … :limit 10]` returns at most 10 rows of the answer, and the engine stops reading once it has them: over 10M facts `:limit 10` reads one internal batch. Without `:order-by` (PR 2) which rows is unspecified, and may differ between plans; they are always rows of the unlimited answer. `:limit 0` returns no rows. It applies after aggregates and windows, to rule queries and to cursors, and a prepared query takes `:limit $n`, bound with `BindValue::Val(Value::Integer(n))`. A value that is not an integer `>= 0` or a slot fails with the new `PRS-115`; a repeated `:limit` with `INT-012` and a missing value with `INT-013`, as for the other query options. `:max-results` and `:max-derived-facts` still limit only the facts rules derive. +- **`:limit N` bounds the rows a query returns** (#306). `[:find … :where … :limit 10]` returns at most 10 rows of the answer, and the engine stops reading once it has them: over 10M facts `:limit 10` reads one internal batch. Without `:order-by` which rows is unspecified, and may differ between plans; they are always rows of the unlimited answer. `:limit 0` returns no rows. It applies after aggregates and windows, to rule queries and to cursors, and a prepared query takes `:limit $n`, bound with `BindValue::Val(Value::Integer(n))`. A value that is not an integer `>= 0` or a slot fails with the new `PRS-115`; a repeated `:limit` with `INT-012` and a missing value with `INT-013`, as for the other query options. `:max-results` and `:max-derived-facts` still limit only the facts rules derive. +- **`:order-by` and `:offset`** (#306). `:order-by [(count ?e) :desc ?name]` orders the rows a query returns by `:find` elements (plain variables, or aggregates and windows written as in `:find`), each `:asc` (the default) or `:desc`; ties are broken by the other `:find` columns ascending, so every position of an ordered answer is decided and every plan returns the same list. Values compare as windows and `min`/`max` compare them: numbers by value (an integer before an equal float, `-0.0` before `0.0`, NaN after every number), then strings, booleans, refs, keywords, `nil` and sets. `:offset N` skips the first `N` rows of the ordered answer, before `:limit`, so `:offset 20 :limit 10` is the third page of ten. A new `Sort` operator reads its whole input; under a `:limit` it keeps only the best `offset + limit` rows, so `:order-by [?v :desc] :limit 10` over 10M facts holds ten rows, not ten million. It applies after aggregates and windows, to rule queries, cursors and prepared queries (`:offset $o`, bound like `:limit`), and counts toward `query_memory_limit`. New codes: `PRS-116` (`:offset` without `:order-by`: without an order, pages could overlap or miss rows), `PRS-117` (an entry that is not a `:find` element) and `PRS-118` (`:order-by` is not a non-empty vector, names an element twice, or has a misplaced or unknown keyword). `PRS-115` now also covers `:offset`. Inside a window's `:over`, `:order-by` is unchanged. - **Set values: `#{...}`** (#316, PR 1 of 3). A fact's value can be a finite set of scalars, `[:alice :user/scopes #{:scope/read :scope/write}]`, written in query text, returned as `Value::Set(ValueSet)`, transacted, retracted and queried by exact value (`[?e :user/scopes #{:scope/write :scope/read}]`), joined on and grouped by. Duplicates are removed and element order does not matter. Two elements are the same when `Value`'s order says so: `0.0` and `-0.0` are one element (`-0.0` is kept), every NaN is one element, a keyword never equals a ref and `1` never equals `1.0`. A set cannot hold a set (`ValueSet::new` fails with the new `API-021`; in query text, `PRS-119`); its elements are literals only (`PRS-120`), and an unclosed `#{` is `PRS-121`. In format v8 a set has value tag `0x08`, after refs; a set whose encoded elements take at most 64 bytes is stored in its index keys, a longer one once in a value page, as a long string is. On a file database a stored set may take up to 4,068 bytes, counting each keyword element as 6 bytes and each ref as 10 (`WAL-003`). The REPL prints sets as `#{...}` and `BrowserDb` returns them as JSON arrays, in `Value`'s order. - **Set-membership predicates** (#316, PR 2 of 3). `[(in? ?role #{:role/admin :role/owner})]` keeps rows whose value is in a set, and `not-in?`, `any-in?` (the two sets share an element), `all-in?` (every element of the first is in the second) and `none-in?` (they share none) complete the five. Each works as a filter or binds a Boolean, `[(any-in? ?scopes #{:scope/write}) ?can-write]`, and takes literal sets, set-valued attributes and bind slots (`BindValue::Val(Value::Set(..))`). Membership is set equality, as for set values: `0.0` is in `#{-0.0}`, NaN is in a set holding NaN, a keyword is not a ref. `in?` of an empty set is false and `not-in?` true; `all-in?` and `none-in?` of an empty first set are true and `any-in?` false. A set where a scalar is needed, or a scalar where a set is needed, is a type mismatch: the filter drops the row and the binding binds nothing, so `not-in?` with a non-set is never true. `contains?` stays string-only. The five names cannot be registered as functions. - **`collect-set`** (#316, PR 3 of 3). `[(collect-set ?e :user/scope) ?scopes]` binds, per row, the set of the values of `[?e :user/scope ?v]` under the query's `:as-of` and `:valid-at`, with retractions applied as for that pattern, and `#{}` when there are none (the row is kept). Combine it with the set predicates: `[(collect-set ?e :user/scope) ?s] [(in? :scope/admin ?s)]`. `?e` must be bound by an earlier clause (`INT-018`); a keyword names its entity, and a value that is no entity gives `#{}`. It works in `:where`, rule bodies, `not-join` bodies and `or` branches; when its output variable is already bound, it keeps the rows where the two sets are equal. It reads stored facts only, never a rule's derived facts. New codes: `PRS-122` (no output variable), `PRS-123` (an operand that is not a `?variable` then an attribute keyword, a bind slot included) and `QRY-015` (a value found is itself a set: bind a set-valued attribute with a pattern). The set it builds counts toward `query_memory_limit` (`QRY-012`). `collect-set` is read only as a whole clause (`PRS-067` inside another expression) and cannot be registered as a function. diff --git a/CLAUDE.md b/CLAUDE.md index 6bf4975e66..ce7a24c964 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -16,7 +16,7 @@ Minigraf follows the "SQLite for bi-temporal graph databases" philosophy: - **Zero-configuration** - No setup, no config files, just works - **Embedded-first** - Library not server, in-process execution - **Single-file database** - One portable `.graph` file -- **Self-contained** - Minimal dependencies, small binary (~1.2MB budget as of #277; see PHILOSOPHY.md §4) +- **Self-contained** - Minimal dependencies, small binary (~1.2MB budget as of #277, 1,230 KiB enforced on v3 since #306; see PHILOSOPHY.md §4) - **Cross-platform** - Native, WASM, mobile, embedded - **Reliability over features** - Do less, do it perfectly - **Bi-temporal first-class** - Time travel is a core feature, not addon @@ -135,20 +135,20 @@ cargo run < demos/demo_negation.txt 3. **`src/query/datalog/`** — Datalog engine - `parser.rs`: EDN/Datalog parser — `transact`, `retract`, `query`, `rule`, `:as-of`, `:valid-at`, `not`, `not-join`; `resolve_pseudo_sources` names each per-fact pseudo-attribute's source (nearest earlier same-entity pattern, lexical scope) and its hidden metadata variable `?#.`, else PRS-081 (#594) - `parser/statement.rs`: `transact`/`retract` read one fact at a time (#550): `kind_of` dispatches on the first two tokens; one pass keeps today's error order (phases 1 tokens … 6 valid windows, the earliest phase's first error, phase 3 in today's check order); `read_statement` (pass 1) keeps at most `TX_CHUNK_FACTS` materialised facts and the offset after the last, and returns phase 5–6 errors from `Statement::facts`/`Statement::chunks` (one `Chunk` at a time; pass 2 from that offset for a larger statement); `set_tx_chunk_facts` for tests (`minigraf::__tx_chunk_facts` and `__statement_facts_high_water` under `test-hooks`). The `Parser` reads tokens on demand from a `Lexer` (`keep` off checks structure without holding it); `parse_transact`/`parse_retract` remain under `cfg(test)` for the differential tests - - `parser/verifier.rs`: test-only (not wasm32) bounded-exhaustive check of the parser against `tests/grammar/grammar.pest` (#643): every 1–3 character string (`parse_edn`) and every balanced token filler up to `MINIGRAF_GRAMMAR_BOUND` (default 3) in 15 command templates (`parse_datalog_command`); pest rejects ⇒ parser rejects, pest accepts ⇒ parser accepts or raises a `SEMANTIC` code; today's drift is `KNOWN_DRIFT`, one entry per cause, removed by its fix (empty: #649, #650, #651 fixed) + - `parser/verifier.rs`: test-only (not wasm32) bounded-exhaustive check of the parser against `tests/grammar/grammar.pest` (#643): every 1–3 character string (`parse_edn`) and every balanced token filler up to `MINIGRAF_GRAMMAR_BOUND` (default 3) in 16 command templates (`parse_datalog_command`); pest rejects ⇒ parser rejects, pest accepts ⇒ parser accepts or raises a `SEMANTIC` code; today's drift is `KNOWN_DRIFT`, one entry per cause, removed by its fix (empty: #649, #650, #651 fixed) - `executor.rs`: `DatalogExecutor` — `transact`/`retract`/`rule` commands, and every query on the engine (`open_query`, `open_rule_query`; planner errors after the pseudo-attribute check, then every predicate the query and its rules name, `QRY-007`); its own query path is gone (#551) - `matcher.rs`: `edn_to_value`, `edn_to_entity_id` - - `aggregate.rs`: `Agg` (one aggregate of one group) and `Running` (a window's running value), used by the engine; exact sums (`i128` integers saturated once, fixed-point floats rounded once), `value_order` (one total order of values for window sorts, peers, `rank` and `min`/`max`), `named_vars` (a window's tie-break variables), `windows` (each window's value per row: partitions, sort, peers) (#547) + - `aggregate.rs`: `Agg` (one aggregate of one group) and `Running` (a window's running value), used by the engine; exact sums (`i128` integers saturated once, fixed-point floats rounded once), `value_order` (one total order of values for window sorts, peers, `rank`, `min`/`max` and `:order-by`), `row_order` (#306), `named_vars` (a window's tie-break variables), `windows` (each window's value per row: partitions, sort, peers) (#547) - `functions.rs`: `FunctionRegistry` (built-ins and UDFs; `Clone` shares the closures), `Functions` — the registry a database shares, `RwLock>`: a query takes a `snapshot()` when it opens and holds no lock while a UDF runs, so UDFs may call back into the database; registration copies, inserts and swaps (#180). `UdfError`: a `try_register_*` closure's failure, `QRY-014`; `eval_expr`'s `EvalError` is `NoValue` (row dropped) or `Udf` (query fails) - `evaluator.rs`: `rule_invocation_to_pattern`, the rule limits and their errors - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection; a positive edge to a rule with `not`/`not-join`/`or`/`or-join` also raises the caller, off a cycle (#628) - `rules.rs`: `RuleRegistry` — thread-safe rule management - - `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `Count` (`:limit` literal or slot, #306), `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper + - `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `Count` (`:limit`/`:offset` literal or slot, #306), `DatalogQuery::order_by` (`:find` elements with `Order`, #306), `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper - `optimizer.rs`: Selectivity-based join reordering on every build (the `wasm` feature is a deprecated no-op). `reorder()` gates every reordering site; tests turn it off per thread (`set_reorder`, `minigraf::__reorder` under `test-hooks`, #596); `plan_seeded` orders a body with its imported variables counted as bound, `plan_after` orders a rule body's clauses after its delta, each joining on a variable bound before it where one can (#694), and `subplans()` lets tests force the engine's negation bodies and `or` branches hashed or correlated (`set_subplans`, `minigraf::__subplans`, #546) - - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute`; `Entity` and `Val(Ref)` fit each other's slots, bind mistakes are `API-022`/`023`/`024` (#181); a `:limit $n` slot takes `Val(Integer(n >= 0))` (`resolve_count_slot`, #306) + - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute`; `Entity` and `Val(Ref)` fit each other's slots, bind mistakes are `API-022`/`023`/`024` (#181); a `:limit $n` or `:offset $o` slot takes `Val(Integer(n >= 0))` (`resolve_count_slot`, #306) - `magic_sets.rs`: Magic-sets rewriting for demand-driven recursive rule evaluation (not applied to rules with `not`/`not-join`) -3a. **`src/query/engine/`** — Streaming query engine (#473), runs every query (#551): `plan.rs` (the operator tree of every query, or the executor's error code for it: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a magic-set head constant is `HeadArg::Const`), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; an `or` branch or a `not` body is planned as a `:where` is; a clause list with no pattern first starts from `Seed`; a constant no cell equals is `Term::Never`, a scan that reads nothing; `:as-of` resolved when the query opens (`Snapshot::tx_bound`: a counter bound when `tx_id` rises with `tx_count`, else `TxBound::Timestamp`: committed `tx_count` ranges and pending `tx_id <= t`); a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, or, under a constant attribute and entity not constant, its value (#721: per outer row the AVET ranges of the values that join-equal it and the attribute's pending facts with its key, read once per query in `IdSpace::probes`; an entity cell needs the keyword naming it, known only where the query made the entity from a keyword (rule heads, magic seeds), else the join becomes the planner's `HashJoin`); `HashJoin` otherwise, and on a relation; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `collect.rs` (`CollectSet`, #316: `[(collect-set ?e :a) ?s]` per row probes `[e :a ?v]` as an `IndexNestedLoopJoin` does and binds the values as one set, `#{}` when none, metered; `Expr::CollectSet`, parsed only as a whole binding clause), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `limit.rs` (`Limit`, #306: skips `offset` rows, passes on at most `limit`, then closes its child so nothing below reads more; planned after the last step, after `Builder::finish`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `meter.rs` (#549: one `Meter` per query, shared by every holder of state through a `Held` — hash join build sides, `not`/`or` tables, distinct sets, aggregate groups, window rows, rule relations and their temporaries, `IdSpace`, the set a `CollectSet` builds; each entry charged by a per-entry estimate before it is inserted, containers grown with `try_reserve`, released on `rewind`/`close`/drop; over `OpenOptions::query_memory_limit`, or a refused allocation, is `QRY-012`; `Stream::close` drops the operator tree, keeping its counters). `mod.rs`: `Operator` (`next_batch`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` run every query on it: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. +3a. **`src/query/engine/`** — Streaming query engine (#473), runs every query (#551): `plan.rs` (the operator tree of every query, or the executor's error code for it: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a magic-set head constant is `HeadArg::Const`), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; an `or` branch or a `not` body is planned as a `:where` is; a clause list with no pattern first starts from `Seed`; a constant no cell equals is `Term::Never`, a scan that reads nothing; `:as-of` resolved when the query opens (`Snapshot::tx_bound`: a counter bound when `tx_id` rises with `tx_count`, else `TxBound::Timestamp`: committed `tx_count` ranges and pending `tx_id <= t`); a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, or, under a constant attribute and entity not constant, its value (#721: per outer row the AVET ranges of the values that join-equal it and the attribute's pending facts with its key, read once per query in `IdSpace::probes`; an entity cell needs the keyword naming it, known only where the query made the entity from a keyword (rule heads, magic seeds), else the join becomes the planner's `HashJoin`); `HashJoin` otherwise, and on a relation; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `collect.rs` (`CollectSet`, #316: `[(collect-set ?e :a) ?s]` per row probes `[e :a ?v]` as an `IndexNestedLoopJoin` does and binds the values as one set, `#{}` when none, metered; `Expr::CollectSet`, parsed only as a whole binding clause), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `sort.rs` (`Sort`, #306: the `:find` columns as values, in the full order of `:order-by` — its keys, then every other `:find` column ascending, by `datalog::aggregate::row_order`/`value_order`; under a `:limit` a heap of the best `offset + limit` rows; reads its whole input, dropping the DICT lookups after each batch, metered; its rows turned back into cells only as returned), `limit.rs` (`Limit`, #306: skips `offset` rows, passes on at most `limit`, then closes its child so nothing below reads more; planned after the last step, after `Builder::finish`, and after `Sort`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `meter.rs` (#549: one `Meter` per query, shared by every holder of state through a `Held` — hash join build sides, `not`/`or` tables, distinct sets, aggregate groups, window rows, rule relations and their temporaries, `IdSpace`, the set a `CollectSet` builds; each entry charged by a per-entry estimate before it is inserted, containers grown with `try_reserve`, released on `rewind`/`close`/drop; over `OpenOptions::query_memory_limit`, or a refused allocation, is `QRY-012`; `Stream::close` drops the operator tree, keeping its counters). `mod.rs`: `Operator` (`next_batch`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` run every query on it: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) @@ -216,7 +216,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1838 tests** (1824 passing, 14 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**1856 tests** (1842 passing, 14 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/PHILOSOPHY.md b/PHILOSOPHY.md index f847bf099b..6cfd02e2c3 100644 --- a/PHILOSOPHY.md +++ b/PHILOSOPHY.md @@ -113,7 +113,9 @@ SQLite's success comes from a clear philosophy: be a library, not a server. Be s #277's structured error codes — 130 documented codes across 6 categories cannot fit in 1MB even with opt-level="z", LTO, codegen-units=1, and strip=symbols all already applied; see CI's `binary-size.yml` for the - enforced limit) + enforced limit). v3.0.0 raises the enforced limit to 1,230 KiB for + `:order-by`/`:offset` and the top-k `Sort` (#306), whose ~11 KiB did not + fit the 2 KiB left after the streaming engine (#473) and set values (#316) - No runtime dependencies (no JVM, no Python, no Node.js) **Anti-pattern**: Requiring external services, libraries, or runtimes to function. diff --git a/README.md b/README.md index dd8c562770..578502efb2 100644 --- a/README.md +++ b/README.md @@ -23,7 +23,7 @@ Minigraf is a **single-file embedded graph database** that lets you: - ✅ **Query relationships with Datalog** - Recursive rules, natural graph traversal - ✅ **Time travel through history** - Bi-temporal queries (transaction time + valid time) - ✅ **Window functions** - `sum/count/min/max/avg/rank/row-number :over (partition-by … :order-by …)` in `:find` clauses -- ✅ **Bounded results** - `:limit N` returns at most N rows and stops the work once it has them +- ✅ **Bounded and ordered results** - `:limit N` returns at most N rows and stops the work once it has them; `:order-by [?score :desc] :limit 10` keeps only the top ten as it reads, and `:offset` pages through an ordered answer - ✅ **Prepared statements** - Parse + plan once with `$slot` bind tokens, execute thousands of times - ✅ **Embed anywhere** - Native, WASM, mobile, IoT - one `.graph` file - ✅ **Zero configuration** - Just `Minigraf::open("data.graph")` and you're done diff --git a/ROADMAP.md b/ROADMAP.md index a44de3562d..8ec88edcdc 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -94,7 +94,7 @@ Scope — format and storage integrity: Scope — query API: - Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) runs every query and produces rows as they are pulled: patterns, expressions and pseudo-attributes (#544), joins and `:db/valid-at` (#545), `not` and `or` (#546), aggregates and windows (#547), rules (#548), and transaction reads (#550); the executor's query path is gone (#551; done on `v3`). Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549). -- Native `:limit N` (done on `v3`, with the 10M-fact acceptance test moved from #473), then `:order-by` and `:offset` with a top-k `Sort` (#306; spec `docs/superpowers/specs/2026-10-24-limit-order-by-design.md`). +- Native `:limit N`, `:order-by` and `:offset`, with a top-k `Sort` whose memory follows `N` (#306; done on `v3`, with the 10M-fact acceptance tests moved from #473; spec `docs/superpowers/specs/2026-10-24-limit-order-by-design.md`). Skipping the sort when an index already returns the rows in order is #641 (v3.next). - Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log pins its generation: checkpoints run but do not reuse its pages (#543; `API-013` deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462. - Read-only open: `OpenOptions::read_only` takes a shared lock, so several readers can hold a file at once, writes nothing to the file or its WAL (a WAL is applied in memory, a v7 file is read without migrating), and refuses writes with `API-014` (#429; Rust API done on `v3`). The bindings' `open_with_options` follows. - Raw log writer: `LogWriter` builds a new database from `FactRecord`s with their `tx_count`, `tx_id`, valid-time windows and assertion flags kept, gaps allowed (a purged transaction stays a hole for `:as-of`), at `.partial` renamed into place by `finish` (#431; Rust API done on `v3`). Completes extract (#429, #430), transform, load. The binding objects follow. diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index 5bb4aac1e5..dbb7be25f7 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -194,6 +194,8 @@ Measuring this found that `Aggregate` built its sorted map of groups uncharged w `limit` is `attribute_scan` with `:limit 10`: `Limit` closes the scan after its first internal batch, so the time does not grow with the facts (p50 307 µs, 317 µs and 318 µs at 100K, 1M and 10M, 5 MiB peak RSS each; `attribute_scan` reads the whole attribute in 43 ms, 462 ms and 4.83 s). Same idle server, one NUMA node, 2026-10-24. The acceptance test (`cargo test --profile bench --test limit_acceptance_test -- --ignored --nocapture`, nightly) runs `:limit 10` over 10M facts of one attribute in 0.8 ms under a 64 KiB `query_memory_limit`, adding 132 KiB of RSS. +`top_k` is `attribute_scan` with `:order-by [?a :desc] :limit 10`: `Sort` reads the whole attribute but holds ten rows, so its time follows the scan and its memory does not (p50 22.4 ms, 241 ms and 2.54 s at 100K, 1M and 10M against `attribute_scan`'s 23.1 ms, 250 ms and 2.63 s on the same run; 6–7 MiB peak RSS at every scale). Same server, one NUMA node, 2026-10-25. The acceptance test runs `:order-by [?v :desc] :limit 10` over the same 10M facts in 28.5 s (bench profile, opt-level `z`) under a 1 MiB `query_memory_limit`, adding no measurable RSS. Skipping the read when an index returns the rows in order is #641. + ### Executor removal (#551) Since #551 every query runs on the engine and the executor's query path is gone. Before it, the queries the engine could not plan ran on the executor, which reads every fact of the patterns' attributes into memory; the envelope's case is `:as-of` with a time. `as_of_ts` is the `as_of` point query with `:as-of "