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
3 changes: 2 additions & 1 deletion CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -59,7 +59,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
- **Single-pattern queries run on a new streaming engine** (#473, part 2: #544, first PR). A query whose `:where` is one pattern and whose `:find` holds plain variables now runs on operators that read index keys in batches of 1,024 rows and turn ids into values only for the rows they return (#530, for these queries). A pattern with a constant attribute and value, `[?e :a C]`, reads the AVET range of `C` instead of every fact of the attribute (#518). Measured at 1M facts (#394 envelope, `[?e :name "…"]`): 344 ms → 20 µs and 142 → 3 MiB; an attribute scan of 166,666 rows 577 → 268 ms and 172 → 57 MiB; point and `:as-of` queries 10–30 % faster. Every other query, and reads inside a `WriteTransaction`, run on the existing executor as before. Results are unchanged: in tests, every query the engine runs is also run by the executor and the answers must agree, and CI runs the whole suite that way (`test-oracle` feature).
- **Expressions and pseudo-attributes run on the streaming engine** (#473, part 2: #544, second PR). The engine now also runs expression clauses after its pattern (`[(> ?v 21)]`, `[(+ ?v 1) ?w]`, registered predicates), per-fact pseudo-attribute patterns on the pattern's entity (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`), and keyword, UUID and float constants in the value position. A constant reads only the AVET ranges it can match: a keyword reads its own range and the range of refs to the entity it names, a UUID reads its ref range and the attribute's keywords, a float reads the attribute's floats. The executor's matching rules are kept (a keyword matches a ref to the entity it names, a UUID matches a keyword that names it, floats match within `f64::EPSILON`), and so are its errors (INT-026, QRY-007). `:db/valid-at`, which the executor matches against every fact of the entity, stays on the executor until joins (#545).
- **Cursors stream the queries the engine runs** (#473, part 2: #544, third PR). `Minigraf::query`, `PreparedQuery::query` and `BrowserDb.query` no longer compute the whole answer at open for these queries: the cursor pulls one batch of up to 1,024 rows from the engine's operators when it runs out of rows, and `close` or dropping it stops the work. An attribute scan drained with `next_batch(1000)` holds 7 MiB at 1M and 10M facts (was 58 and 458 MiB) and runs 3–17 % faster (#394 envelope). The answer is still the database as it was when the cursor opened, whatever is written or checkpointed while it is open. A read error that happens after some rows of a `next_batch` call were gathered is returned by the next call, after those rows. No API change.
- **Joins run on the streaming engine** (#473, part 3: #545, second PR). Queries of several patterns with stored attributes, with or without expression clauses, now run on the engine. Patterns run in the planner's order: the first is a scan, and each later one is an `IndexNestedLoopJoin` when its entity is a variable already bound (one entity range per row, committed and pending), or a `HashJoin` otherwise (value and attribute positions, cross products), built on the side with the smaller estimate. Joins follow the executor's rules (#545, first PR): floats are equal by IEEE `==`, a keyword equals a ref to the entity it names, and a variable keeps the value of its first pattern in the `:where` text. Measured at 1M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n]` 796 ms → 50 µs and 322 → 4 MiB; `[:p :manager ?b] [?s :manager ?b] [?s :name ?n]` 1.67 s → 148 ms and 392–462 → 14 MiB; `[?e :follows ?f] [?f :group 7] [?f :name ?n]` 2.6 s → 1.1 s and 468–480 → 42 MiB. Pseudo-attribute patterns in a query of several patterns, `:db/valid-at`, `or`, `not`, rules and aggregates still run on the executor. Results are unchanged (`test-oracle`).
- **Joins run on the streaming engine** (#473, part 3: #545, second PR). Queries of several patterns with stored attributes, with or without expression clauses, now run on the engine. Patterns run in the planner's order: the first is a scan, and each later one is an `IndexNestedLoopJoin` when its entity is a variable already bound (one entity range per row, committed and pending), or a `HashJoin` otherwise (value and attribute positions, cross products), built on the side with the smaller estimate. Joins follow the executor's rules (#545, first PR): floats are equal by IEEE `==`, a keyword equals a ref to the entity it names, and a variable keeps the value of its first pattern in the `:where` text. Measured at 1M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n]` 796 ms → 50 µs and 322 → 4 MiB; `[:p :manager ?b] [?s :manager ?b] [?s :name ?n]` 1.67 s → 148 ms and 392–462 → 14 MiB; `[?e :follows ?f] [?f :group 7] [?f :name ?n]` 2.6 s → 1.1 s and 468–480 → 42 MiB. `or`, `not`, rules and aggregates still run on the executor. Results are unchanged (`test-oracle`).
- **Pseudo-attributes across joins and `:db/valid-at` run on the streaming engine** (#473, part 3: #545, third PR). A per-fact pseudo-attribute pattern (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`) reads, as the executor does, the fact of the last pattern before it in the planner's order that matched its entity: the scans of those patterns fill metadata columns and the pattern picks one per row. The engine runs it when its entity term is the entity term of an earlier pattern, or when no pattern with a stored attribute runs before it; then, and for every `:db/valid-at` pattern, it joins with every visible fact of its entity, as `[e _ _]` would, with the metadata or the query's valid time as a column. Other shapes (a pseudo-attribute pattern on an entity that no earlier pattern has as its entity, a `_` entity) stay on the executor; that the answer depends on the plan order is tracked in #594. Measured at 10M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n] [?f :db/tx-count ?t]` 34 s → 56 µs and 6.0–7.5 GiB → 4 MiB (3.2 s → 56 µs at 1M). Results are unchanged (`test-oracle`).
- **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.

Expand Down
2 changes: 1 addition & 1 deletion CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -139,7 +139,7 @@ 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 with stored attributes and expression clauses in `optimizer::plan` order, or one pattern with per-fact pseudo-attribute patterns on its entity; 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 columns 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), `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
2 changes: 1 addition & 1 deletion ROADMAP.md
Original file line number Diff line number Diff line change
Expand Up @@ -93,7 +93,7 @@ Scope — format and storage integrity:

Scope — query API:

- Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) produces rows as they are pulled for the queries it runs (one pattern with expressions and pseudo-attributes, #544; joins of patterns and expressions, #545); pseudo-attributes across joins, negation, aggregates, rules and transaction reads move to it in #545–#551, without API changes. Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549).
- Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) produces rows as they are pulled for the queries it runs (one pattern with expressions and pseudo-attributes, #544; joins of patterns, expressions and pseudo-attributes, `:db/valid-at`, #545); negation, aggregates, rules and transaction reads move to it in #546–#551, without API changes. Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549).
- Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log pins its generation: checkpoints run but do not reuse its pages (#543; `API-013` deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462.
- Read-only open: `OpenOptions::read_only` takes a shared lock, so several readers can hold a file at once, writes nothing to the file or its WAL (a WAL is applied in memory, a v7 file is read without migrating), and refuses writes with `API-014` (#429; Rust API done on `v3`). The bindings' `open_with_options` follows.
- Raw log writer: `LogWriter` builds a new database from `FactRecord`s with their `tx_count`, `tx_id`, valid-time windows and assertion flags kept, gaps allowed (a purged transaction stays a hole for `:as-of`), at `<path>.partial` renamed into place by `finish` (#431; Rust API done on `v3`). Completes extract (#429, #430), transform, load. The binding objects follow.
Expand Down
16 changes: 15 additions & 1 deletion docs/BENCHMARKS.md
Original file line number Diff line number Diff line change
Expand Up @@ -114,7 +114,21 @@ Queries of several patterns run on the engine since #545 PR 2: an `IndexNestedLo
| `join_3_scan` peak RSS | 48–67 → 14 MiB | 468–480 → 42 MiB |
| point, `:as-of`, `:valid-at`, hot entity, attribute scan | unchanged | unchanged |

`join_2` probes one entity's range for its one outer row. `join_3_selective` joins on the value position, so it is a `HashJoin` that reads every `:manager` fact into its table: a value probe would need AVET over pending facts, which the pending store does not have (decision 3 of the #545 plan). `join_3_scan` scans the AVET range of `:group 7`, joins `:follows` on its value with a `HashJoin` built on those rows (it streams every `:follows` fact), then probes `:name` per row. 10M runs with #545's last PR.
`join_2` probes one entity's range for its one outer row. `join_3_selective` joins on the value position, so it is a `HashJoin` that reads every `:manager` fact into its table: a value probe would need AVET over pending facts, which the pending store does not have (decision 3 of the #545 plan). `join_3_scan` scans the AVET range of `:group 7`, joins `:follows` on its value with a `HashJoin` built on those rows (it streams every `:follows` fact), then probes `:name` per row.

At 10M facts with PR 3 (same server, two rounds; the PR 2 code is unchanged for these shapes, and both builds agree within 2%): `join_2` 51 µs and 4 MiB; `join_3_selective` 2.48–2.52 s and 66 MiB, its `HashJoin` table holding the 10M-fact graph's 1.67M `:manager` facts; `join_3_scan` 13.6 s and 59–63 MiB. The 10M figures in the first table above, before #545 and on the laptop, are 6.50 s, 13.5 s and 20.9 s with 2.3–3.6 GiB of RSS.

#### Pseudo-attributes across joins (#545 PR 3)

`join_2_pseudo` is `[:p{m} :follows ?f] [?f :name ?n] [?f :db/tx-count ?t]` with `:valid-at :any-valid-time` (1 row). Before PR 3 a pseudo-attribute pattern in a query of several patterns sent the whole query to the executor, which materialises every fact. A/B on the same idle server, `v3` (86ad20b, with the envelope shape added) on one socket and PR 3 on the other, swapped for the second round; p50 of each round, peak RSS.

| `join_2_pseudo` | 100K | 1M | 10M |
|---|---:|---:|---:|
| p50, `v3` → PR 3 | 211 ms → 40–58 µs | 3.19 s → 55–56 µs | 33.8–34.1 s → 56 µs |
| peak RSS | 122 → 4 MiB | 857–858 → 4 MiB | 6.0–7.5 GiB → 4 MiB |
| every other shape | unchanged | unchanged | unchanged |

The pseudo-attribute pattern reads the `:db/tx-count` column that the `:name` probe fills for its one row.

### Python FFI round trip

Expand Down
Loading
Loading