Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
4 changes: 3 additions & 1 deletion CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -22,7 +22,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
- **An unknown aggregate or window function is an error whatever the data** (#414). Aggregate and window function names in `:find` are now resolved before the query runs: an unknown aggregate fails with the new `QRY-010` and an unknown window function with the new `QRY-011`, even on an empty database or when no row matches. Before, such a query returned no results until a row matched and then failed with `INT-029`/`INT-030`, which stay registered for internal inconsistencies only.
- **One current valid-time window per fact** (#435). At any transaction time, each `(entity, attribute, value)` now has exactly one current valid-time window: the one from its latest `transact`. A later assertion of the same fact replaces the earlier window, which stays visible through `:as-of` of the earlier transaction. Before, every window ever asserted stayed live until a `retract`, so closing an open window with `(transact {:valid-from vf :valid-to D} ...)` left the open one live and `:valid-at` after `D` still found the fact. Closing, extending or reopening a window is now a plain `transact` with the new bounds; `retract` still withdraws the fact. **This changes query results for existing data:** a fact asserted in several transactions with different windows is now valid only in its latest window at the current transaction time. A fact that was true over two separate periods can no longer have both windows live at once; model each period as its own entity, or read earlier periods with `:as-of`. Asserting one fact with two different windows in one `transact` is rejected with the new `API-011`, and nothing is written. Data written before this check with two windows in one transaction keeps both.
- **The `uuid` dependency no longer enables `v4`** (#439). The library only makes v5 UUIDs, so the `v4` feature and, on browser wasm, `js` are gone from its `uuid` dependency, and with them `getrandom`. A crate that called `Uuid::new_v4` only because Cargo feature unification turned `v4` on through minigraf must now enable `uuid/v4` itself. The release binary shrinks by 48 bytes.
- **Join answers no longer depend on the query plan** (#545). Two cases changed. A join on a float value now pairs `0.0` with `-0.0`, as a shared variable compared after the join key already did; before, `Value`'s hash told them apart, so the join key never paired them. NaN still equals nothing. Float constants in a pattern still match within `f64::EPSILON`. And a variable bound to a keyword by one pattern and to the ref of the entity the keyword names by another, which already joined, now returns the kind from the first of those patterns in the `:where` text. Before, it returned the kind from the pattern the planner ran first, so the answer could change with the selectivity of the other patterns, and differed under the `wasm` feature, which does not reorder. For example, with `[:alice :friend :bob]` stored as a keyword, `[:find ?b :where [?a :friend ?b] [?b :name "Bob"]]` returned the ref of `:bob`, because the planner runs the pattern with two constants first, and now returns the keyword `:bob`. An expression that binds a variable still sets its value where it runs, and later patterns keep that value. The rule covers the top-level `:where` of queries with and without rules; inside `or`, `not` and rule bodies the kinds are unchanged.
- **Join answers no longer depend on the query plan** (#545). Two cases changed. A join on a float value now pairs `0.0` with `-0.0`, as a shared variable compared after the join key already did; before, `Value`'s hash told them apart, so the join key never paired them. NaN still equals nothing. Float constants in a pattern still match within `f64::EPSILON`. And a variable bound to a keyword by one pattern and to the ref of the entity the keyword names by another, which already joined, now returns the kind from the first of those patterns in the `:where` text. Before, it returned the kind from the pattern the planner ran first, so the answer could change with the selectivity of the other patterns, and differed under the `wasm` feature, which does not reorder. For example, with `[:alice :friend :bob]` stored as a keyword, `[:find ?b :where [?a :friend ?b] [?b :name "Bob"]]` returned the ref of `:bob`, because the planner runs the pattern with two constants first, and now returns the keyword `:bob`. Expression bindings follow the next entry (#596). The rule covers the top-level `:where` of queries with and without rules; inside `or`, `not` and rule bodies the kinds are unchanged.
- **An expression binding a variable that another clause binds keeps only the rows where the two agree** (#596). `[(f …) ?x]` used to overwrite `?x` wherever the planner ran it, so when a pattern also bound `?x` the answer depended on whether that pattern ran first, and differed under the `wasm` feature, which does not reorder. Now the expression unifies: the row is kept when its result equals `?x`'s value, with the join equality of #545 (floats by IEEE `==`, a keyword equal to a ref to the entity it names, an integer never equal to a float, NaN equal to nothing). For example, with `[:a :age 30] [:b :age 40] [:p1 :score 41]`, `[:find ?a ?x :where [?e :age ?a] [:p1 :score ?x] [(+ ?a 1) ?x]]` returned `[30 31] [40 41]` natively and now returns `[40 41]`, as it did under `wasm`. `[(+ ?v 1) ?v]` never matches, and two expressions binding one variable must agree. When the two values differ only as keyword and ref, the variable returns the value of the first clause in the `:where` text that binds it, expressions included. This applies to `or` branches, `not` bodies and rule bodies too, on the executor and on the streaming engine.

### Added

Expand Down Expand Up @@ -75,6 +76,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
- **Weekly soak test at scale (#392).** `tests/soak_test.rs` grows a file-backed database to 10M live facts in batches of 1–2,000 facts (multi-valued tags and shard values in one transaction, strings over 64 bytes, refs), then churns it for the rest of a 5-hour budget at 50 transactions a second: retracts and re-asserts of random facts, and long retract/assert histories on 32 hot entities. It checkpoints every 20–200 transactions and reopens every 2–10 minutes, half from a checkpointed file and half replaying the WAL. Every 10 minutes, after every reopen, and between churn writes it checks samples against a reference that derives each entity's facts from its number and keeps only what was retracted: EAVT per entity, entity and attribute on the tags, AVET by unique name, AEVT over a sparse attribute, `:as-of` on hot entities, and the transaction counter; a full scan runs in a child process at 2M facts (so its memory does not hide a leak), and `verify()` at the end. It fails if RSS after a reopen grows past 1.25× the baseline plus 256 MiB. Metrics (file size, open and checkpoint time, RSS and peak RSS, p50/p99 per query path) go to a JSON-lines file that `.github/workflows/soak.yml` uploads weekly, alternating `main` and `v3`. `soak_short` runs the same driver at 20K facts in the per-PR suite. Found #518: attribute-and-value patterns scan the whole attribute.
- **Coverage gates that gate (#396).** The per-module gate in `coverage-gates.yml` had never checked anything: the instrumented test run failed (the lock tests could not find `pid_ns_helper`), the report it grepped was empty, and every module was skipped with a warning, so the job passed. It also read `cargo llvm-cov --text`, which has no per-file percentages, and named `btree_v6`, which v3 no longer has. The job now runs the whole suite with branch coverage on a pinned nightly, fails if any test fails, and checks each file's line and branch percentage against `coverage-thresholds.toml` with `scripts/coverage_gates.py`; a file missing from the report, or without branch data, fails. The thresholds file covers the WAL, `db.rs`, the fact log and log writer, every storage file, and the evaluator, executor and stratification, with floors at the measured values less one point. It also lists the paths left uncovered on purpose (invariant checks, browser-only and Windows-only paths). New tests cover the WAL's fact-size and fact-count limits (the old fact-size test changed bytes inside the fact and never reached the limit), a WAL opened in a missing directory, a failed cut of a torn WAL tail, short v7 pages and slots past the count, backup meta pages of another generation or length, a torn first meta with data in page 1, `save` with nothing pending, `into_backend` with pending facts, `rebuild_indexes` with nothing checkpointed, unsorted or repeated B+tree input, a stored key inserted with another value, a tree pointer to a page of another type, the read-only `MutexStorageBackend`, and two threads missing the same page in the page cache (before, only a lucky race reached that path). Branch coverage of `wal.rs` went from 83% to 95%, `packed_pages.rs` from 86% to 100%, `persistent_facts.rs` from 82% to 88%, and `btree.rs` from 85% to 85.5%. A follow-up brought the storage files the issue named to 90% branch coverage or more: `btree.rs` to 95.7%, `persistent_facts.rs` to 91.7% and `index.rs` to 100%, with floors raised to match. New tests cover a leaf packing retried around one large entry, an entry larger than a page, separators over the fill target, an insert into a tree whose root points to itself, auto-save on drop, a torn first meta with a blank page 1, and an unreadable page past the meta's page count. Splitting internal nodes is now one pass: the old retry loop could not run, because the balanced cut always leaves each node within the fill target. The workflow pins cargo-llvm-cov 0.9.1, since 0.8.x missed the library's unit tests under the pinned nightly and reported much lower numbers.
- **Performance envelope at 100K–10M facts (#394).** `examples/perf_envelope.rs` builds and caches fixtures of 100K, 1M and 10M facts (six attributes per entity, a ref tree, two valid-time windows, an entity with 1,000 versions). It reports open and checkpoint times, RSS, and p50/p99 latency for twelve query shapes, each shape in its own process. It builds with a new `envelope` Cargo profile (`release` at opt-level 3, as an application compiles the library; `release` itself is opt-level "z"). `docs/BENCHMARKS.md` and the README publish the results: point lookups and single-entity time travel stay flat (12–14 µs at 10M facts). Scans, aggregations and joins grow linearly with the attributes they touch. Rule queries are supported to 100K facts only. A Python FFI round trip (`bench/envelope.py` in minigraf-python) adds about 70 µs per query. `.github/workflows/envelope.yml` runs 100K and 1M on demand, and a 10K smoke pass on PRs that change the harness. The nightly Criterion `query/*` groups gain 100K and 1M scales. Profiling at 1M facts found #528, #529, #530, #531 and #532.
- **Answers that depend on the plan fail the tests (#596).** A test-only switch (`minigraf::__reorder`, `test-oracle` feature) turns off every place the native build reorders: the pattern selectivity sort, the `not`/`not-join` and `or`/`or-join` cost sorts and the `or` short-circuits (#250), and the engine's `HashJoin` build side. `tests/plan_independence_test.rs` runs a matrix of queries (joins, expressions, rules, `or`/`or-join`, `not`/`not-join`, keyword and ref, floats, long strings, aggregates, time travel), in memory and on file, through `execute` and a cursor, with the switch on and off, and requires the same rows. Under `test-oracle` the model-based (#385) and property (#386) tests also run every generated query with the switch off.
- `tests/snapshot_atomicity_test.rs` races a writer against a reader: a query must see each transaction whole, whether written with `execute` or a `WriteTransaction` (#554), and must read one state for all its patterns (#555), in memory and on file. It also runs the v2.x checkpoint race from #558, which never failed on v3: copy-on-write checkpoints do not overwrite pages a published reader uses.
- **The `datalog_eval` fuzz guard counts partial bindings** (#597). The guard skipped inputs whose patterns join to more than 50,000 rows, counting only the rows after the last pattern. A `not-join` body still runs on the executor pattern by pattern in text order, so a 120-pattern body built hundreds of thousands of partial bindings before its last pattern matched nothing, and ran past the 60-second timeout. The guard now counts the bindings after every pattern. On the `v3` corpus (4,783 inputs) coverage drops by 7 of 9,719 edges. The input is added as a seed, as is the `btree_page` input of the cursor fix above.

Expand Down
6 changes: 3 additions & 3 deletions CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -135,11 +135,11 @@ cargo run < demos/demo_negation.txt
- `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection
- `rules.rs`: `RuleRegistry` — thread-safe rule management
- `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper
- `optimizer.rs`: Selectivity-based join reordering; disabled under `wasm` feature
- `optimizer.rs`: Selectivity-based join reordering; disabled under `wasm` feature. `reorder()` gates every reordering site; tests turn it off per thread (`set_reorder`, `minigraf::__reorder` under `test-oracle`, #596)
- `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 and expression clauses in `optimizer::plan` order; a pseudo-attribute pattern reads the metadata column of the last earlier pattern that matched its entity, chosen per row, or joins as `[e _ _]` when none runs before it, as `:db/valid-at` always does; plain `:find` variables, today), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; 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), `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), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree). `mod.rs`: `Operator` (`next_batch`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` try it first: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it.
3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: patterns and expression clauses in `optimizer::plan` order; a pseudo-attribute pattern reads the metadata column of the last earlier pattern that matched its entity, chosen per row, or joins as `[e _ _]` when none runs before it, as `:db/valid-at` always does; plain `:find` variables, today), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; 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), `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), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree). `mod.rs`: `Operator` (`next_batch`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` try it first: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it.

4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396)

Expand Down Expand Up @@ -204,7 +204,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**1507 tests** (1497 passing, 10 ignored; unit + integration + doc).
**1514 tests** (1504 passing, 10 ignored; unit + integration + doc).
See `docs/TEST_COVERAGE.md` for the full per-file breakdown.

**Testing conventions** — see the Testing Conventions section below before writing any tests.
Expand Down
2 changes: 1 addition & 1 deletion README.md
Original file line number Diff line number Diff line change
Expand Up @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit

```bash
cargo run # interactive Datalog REPL
cargo test # run 1507 tests
cargo test # run 1514 tests
cargo run < demos/demo_recursive.txt # recursive rules demo
```

Expand Down
5 changes: 3 additions & 2 deletions docs/TEST_COVERAGE.md

Large diffs are not rendered by default.

Loading
Loading