From fa00fc8e08da8ee4ddc4c371dfd3e08948592cf6 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 27 Oct 2026 11:51:54 +0530 Subject: [PATCH 1/2] feat(query): add bounded sliding row frames (#183) --- CHANGELOG.md | 1 + CLAUDE.md | 6 +- README.md | 2 + ROADMAP.md | 2 +- benches/minigraf_bench.rs | 78 +++++ docs/BENCHMARKS.md | 30 +- docs/ERROR_REFERENCE.md | 29 +- docs/GRAMMAR.md | 15 +- docs/TEST_COVERAGE.md | 14 +- docs/benchmarks/183-row-frames.csv | 129 ++++++++ .../plans/2026-10-27-183-row-frames.md | 18 ++ .../specs/2026-10-27-183-row-frames-design.md | 37 +++ src/error.rs | 18 ++ src/query/datalog/aggregate.rs | 228 +++++++++++++- src/query/datalog/aggregate/tests.rs | 133 +++++++++ src/query/datalog/parser.rs | 129 ++++++++ src/query/datalog/parser/verifier.rs | 24 +- src/query/datalog/types.rs | 14 + src/query/engine/tests.rs | 158 ++++++++-- tests/error_codes_qry_test.rs | 16 +- tests/grammar/grammar.pest | 8 +- .../semantic/query_window_rows_rank.edn | 2 + .../syntax/query_window_rows_duplicate.edn | 2 + .../query_window_rows_missing_suffix.edn | 2 + .../valid/query_window_rows_adjacent.edn | 2 + .../valid/query_window_rows_leading_zero.edn | 2 + .../grammar/valid/query_window_rows_zero.edn | 2 + tests/window_functions_test.rs | 279 ++++++++++++++++++ 28 files changed, 1329 insertions(+), 51 deletions(-) create mode 100644 docs/benchmarks/183-row-frames.csv create mode 100644 docs/superpowers/plans/2026-10-27-183-row-frames.md create mode 100644 docs/superpowers/specs/2026-10-27-183-row-frames-design.md create mode 100644 tests/grammar/invalid/semantic/query_window_rows_rank.edn create mode 100644 tests/grammar/invalid/syntax/query_window_rows_duplicate.edn create mode 100644 tests/grammar/invalid/syntax/query_window_rows_missing_suffix.edn create mode 100644 tests/grammar/valid/query_window_rows_adjacent.edn create mode 100644 tests/grammar/valid/query_window_rows_leading_zero.edn create mode 100644 tests/grammar/valid/query_window_rows_zero.edn diff --git a/CHANGELOG.md b/CHANGELOG.md index 7a7334c7ec..2bf3b3769f 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -51,6 +51,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Added +- **Bounded sliding row frames** (#183; v3.next, unreleased). `:rows N preceding` adds a physical-row frame to window aggregates. Keep this change out of v3.0.0. - **`lag` and `lead` window functions** (#182). `(lag ?value :over (:partition-by ?group :order-by ?key))` reads the previous row's value; `lead` reads the next row's. Both use the established total partition order, including named-variable tie breaks, and return `nil` at partition edges. `:desc` reverses the primary key, so the previous row has a higher or equal key. They run over grouped rows after aggregation and before `:distinct`, sorting and pagination. An optional offset or explicit default is not part of this release. The plain `(lag ?v)` and `(lead ?v)` forms remain available to registered user aggregates. `PRS-030` is deprecated and no longer emitted. - **Optional distinct query results** (#493). A bare `:distinct` flag removes repeated final `:find` tuples after aggregates and windows and before `:order-by`, `:offset` and `:limit`. Queries still return bags by default; `:with` keeps its aggregate grouping behavior. Equality follows `count-distinct` (including one NaN and one floating zero), with canonical `-0.0`/NaN output, also inside sets. The distinct keys count toward `query_memory_limit`; ordered top-k queries still retain a key for every unique tuple they encounter. - **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. diff --git a/CLAUDE.md b/CLAUDE.md index 19230f77ab..4b5d7a5bf6 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -135,7 +135,7 @@ 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 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) + - `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 17 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`, `min`/`max` and `:order-by`), `row_order` (#306), `named_vars` (a window's tie-break variables), `windows` (each window's value per row: charged partition indices, in-place total sort, peers) (#547, #765) @@ -216,7 +216,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1887 tests** (1873 passing, 14 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**1900 tests** (1885 passing, 15 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. @@ -228,7 +228,7 @@ See `docs/TEST_COVERAGE.md` for the full per-file breakdown. Current plan (see `ROADMAP.md` and the milestones): - **v2.x** (`main`, format v7) now gets only data-integrity and security fixes as patch releases (v2.0.3 is the first); v2.0.2 was the last planned v2.x release. - **v3.0.0** (format v8 and data integrity, plus `:limit` #306, optional `:distinct` output #493, `lag`/`lead` #182, query profiler #185, set membership predicates #316 and prepared queries in every binding #181, UDF registration in every binding #180; tracker #383) is developed on the long-lived `v3` branch. All v3 PRs target `v3`; `main` stays untouched. CI runs on PRs to `v3` the same as on PRs to `main`. Do not merge `main` into `v3` routinely: `main` only gets backports of fixes already on `v3`. Shared CI and workflow changes land on both branches as separate PRs. Just before the v3.0.0 cut, merge `main` into `v3` once (merge commit; source conflicts resolved to `v3`, `main`'s v2.0.x CHANGELOG sections brought over) so the cut is a fast-forward. At the first v3 release, the current `main` is copied to `v2` and `v3` becomes the new `main`. -- **v3.next** (the release after v3.0.0) holds new features (sliding row frames #183, rule persistence #241, OPFS `BrowserDb` #441). +- **v3.next** (the release after v3.0.0) holds new features (sliding row frames #183, implemented but unreleased; rule persistence #241; OPFS `BrowserDb` #441). - Known v2.x data issue: same-transaction multi-valued facts (#371). Fix ships in v3.0.0. All v2.x known issues are listed in pinned issue #421 (`known-issue` label); `data-integrity`/`corruption`/`durability` issues fixed in a v2.x patch stay open until that patch is published; issues fixed on the unreleased `v3` branch close on merge (closing keywords do not fire on `v3`, so close them with `gh issue close`) and stay listed in #421 (CONTRIBUTING.md). - Support policy and tiers: PHILOSOPHY.md §7 and §10. v2.x gets data-integrity and security fixes for 12 months after v3.0.0. Tier 1 = Rust + Python + browser WASM (from v3.0.0); other bindings are Tier 2. diff --git a/README.md b/README.md index 660286751b..b082d8df15 100644 --- a/README.md +++ b/README.md @@ -30,6 +30,8 @@ Minigraf is a **single-file embedded graph database** that lets you: For example, `(lag ?salary :over (:partition-by ?dept :order-by ?hire-date))` reads the preceding employee's salary within each department; the first row gets `nil`. `lead` reads the following row. +Unreleased #183 work adds bounded sliding windows such as `(avg ?salary :over (:partition-by ?dept :order-by ?hire-date :rows 2 preceding))`. The feature is planned for v3.next and is not in a published release. + **Status**: See [ROADMAP.md](ROADMAP.md) for planned work and current direction. ## Why Datalog? diff --git a/ROADMAP.md b/ROADMAP.md index b9d162ae29..2bf098379a 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -129,7 +129,7 @@ Scope — release-gate testing and documentation: Additive features, kept out of v3.0.0 so the #371 fix is not held up by them: - Rule persistence — design first (#241) -- Sliding row frames — `:rows N preceding` (#183; builds on #182) +- Sliding row frames — `:rows N preceding` (#183; implemented for v3.next, unreleased; hold the PR merge until after the v3.0.0 cut; builds on #182) - OPFS-backed persistent mode for `BrowserDb`: a sync access handle in a dedicated Worker, no in-memory buffer; IndexedDB stays the main-thread backend. Starts at Tier 2 inside the Tier 1 browser binding until it has shipped (#441) - Temporal graph-traversal research (#273; may result in documentation or a blog post rather than code) diff --git a/benches/minigraf_bench.rs b/benches/minigraf_bench.rs index c2801fe5b8..35ac5a1021 100644 --- a/benches/minigraf_bench.rs +++ b/benches/minigraf_bench.rs @@ -1381,6 +1381,83 @@ fn bench_window(c: &mut Criterion) { } } +// #183: bounded row frames against the same dataset's default peer frame. +// Run with `cargo bench --bench minigraf_bench -- window_rows/`. +fn bench_window_rows(c: &mut Criterion) { + for &n in &[10_000usize, 100_000] { + // Criterion calls every bench function even when its filter skips the + // group. Build this fixture only when a window_rows case actually runs. + let db = std::sync::OnceLock::new(); + let partition_len = n / 100; + + for &(shape, partition_by, part_size) in &[ + ("one", "", n), + ("hundred", ":partition-by ?p ", partition_len), + ] { + let sqrt = part_size.isqrt(); + let widths = [ + ("default", None), + ("zero", Some(0)), + ("two", Some(2)), + ("sqrt", Some(sqrt)), + ("half", Some(part_size / 2)), + ("prefix", Some(part_size)), + ]; + for func in ["sum", "count", "min", "max", "avg", "frame_bench_sum"] { + for &(width_name, width) in &widths { + if func == "frame_bench_sum" + && ((n == 100_000 && width_name != "prefix") + || (n == 10_000 && !["zero", "two", "half"].contains(&width_name))) + { + continue; + } + let frame = width.map_or_else(String::new, |w| format!(":rows {w} preceding ")); + let query = format!( + "(query [:find ?e ({func} ?v :over ({partition_by}:order-by ?v {frame})) \ + :where [?e :val ?v] [?e :part ?p]])" + ); + let mut group = c.benchmark_group("window_rows"); + group.sample_size(10); + group.throughput(Throughput::Elements(u64::try_from(n).expect("row count"))); + let id = format!("{n}/{shape}/{func}/{width_name}"); + group.bench_function(BenchmarkId::from_parameter(id), |b| { + let db = db.get_or_init(|| { + let db = helpers::populate_in_memory(n); + // Every comparison sees the same facts, including + // the one hundred equal-sized partition labels. + for start in (0..n).step_by(100) { + let mut command = String::from("(transact ["); + for row in start..(start + 100).min(n) { + command.push_str(&format!( + "[:e{row} :part {}]", + row / partition_len + )); + } + command.push_str("])"); + db.execute(&command).expect("partition facts"); + } + db.register_aggregate( + "frame_bench_sum", + || 0i64, + |sum, value| { + if let minigraf::Value::Integer(v) = value { + *sum += *v; + } + }, + |sum, _| minigraf::Value::Integer(*sum), + ) + .expect("aggregate registration"); + db + }); + b.iter(|| black_box(db.execute(black_box(&query)).expect("window query"))); + }); + group.finish(); + } + } + } + } +} + // ── Temporal metadata queries ───────────────────────────────────────────────── fn bench_temporal_metadata(c: &mut Criterion) { @@ -1906,6 +1983,7 @@ criterion_group!( bench_aggregation, bench_expr, bench_window, + bench_window_rows, bench_temporal_metadata, bench_udf, bench_aggregation_extras, diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index dbb7be25f7..0867864d91 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -2,6 +2,34 @@ This document records reproducible local benchmark snapshots. Completed release-performance history belongs in the [CHANGELOG](../CHANGELOG.md); continuous CI history is available on [Bencher](https://bencher.dev/perf/minigraf/plots). +## Bounded row frames (#183, unreleased) + +**Date**: 2026-10-27 · **Branch**: `feat/183-row-frames` on `v3` · **Machine**: Intel Xeon E5-2696 v4, Linux 6.8, Rust 1.99.1, idle during timing. **Reproduction command**: `numactl --cpunodebind=1 --membind=1 cargo bench --bench minigraf_bench -- window_rows --sample-size 10 --warm-up-time 0.1 --measurement-time 0.2 --nresamples 1000 --noplot`. The recorded run invoked the prebuilt Criterion binary directly with its `--bench` switch after checking the machine was idle. Criterion extended the measurement time for slow cases to obtain ten samples. The committed harness uses the same in-memory facts for a default-frame and each bounded-frame comparison. Each query scans and joins the facts, sorts window input, evaluates one aggregate, and materializes the result. + +The [per-case CSV](benchmarks/183-row-frames.csv) contains the median and full range of the ten per-call samples, plus the peak bytes charged to the query engine's memory meter. The peak comes from the ignored `window_rows_benchmark_meter_peaks` diagnostic using identical fixtures and queries. It is a separate run from Criterion. The timed benchmark process's maximum RSS was 1,671,892 KiB across both fixture sizes; this is a process-wide high-water mark, not a per-query peak. The engine meter omits unrelated process and user-function allocations. + +| Built-in gate | Worst observed | Limit | +|---|---:|---:| +| 100,000 rows: bounded/default median, same function and fixture (`min`, one partition, prefix) | 1.010× | 5× | +| 100,000/10,000 row median, same function, frame and partition shape (`sum`, 100 partitions, `2 preceding`) | 12.885× | 15× | + +At 100,000 rows in one partition, a zero-width `min` frame peaked at 25,600,040 engine-meter bytes, only 8 bytes more than the default frame. Its prefix-covering frame peaked at 26,400,032 bytes, an 800,000-byte deque charge. The corresponding 100-partition deque charges were 8 and 8,000 bytes. This confirms deque memory follows the frame's maximum width rather than always reserving the whole partition. + +The UDF benchmark registers an integer sum with a fresh accumulator per bounded frame. Its middle-sized frames deliberately use replay; a prefix-covering frame uses one running accumulator. Callback counts follow from the frame widths and partition sizes. + +| Rows | Partitions | Frame | Callbacks | Median (ms) | +|---:|---:|---|---:|---:| +| 10,000 | 1 | `0 preceding` | 10,000 | 38.152 | +| 10,000 | 1 | `2 preceding` | 29,997 | 38.275 | +| 10,000 | 1 | `5,000 preceding` | 37,507,500 | 611.494 | +| 10,000 | 100 | `0 preceding` | 10,000 | 38.478 | +| 10,000 | 100 | `2 preceding` | 29,700 | 38.786 | +| 10,000 | 100 | `50 preceding` | 382,500 | 41.717 | +| 100,000 | 1 | prefix-covering | 100,000 | 459.714 | +| 100,000 | 100 | prefix-covering | 100,000 | 467.106 | + +The harness omits the quadratic 100,000-row, half-partition UDF case. The large-case query scan and result materialization dominate the built-in timings; this snapshot checks relative growth of this complete query shape, not isolated deque or sum-step throughput. + ## Performance Envelope (v3.0.0, #394) **Version**: `v3` branch (format v8), unreleased · **Date**: 2026-10-11 · **Command**: `cargo run --profile envelope --example perf_envelope -- --scales 100k,1m,10m` · Intel Core i7-1065G7 (4 cores / 8 threads, 16 GB RAM), Rust 1.94.0, Linux 6.12.108, on AC power and otherwise idle; the `.graph` file on an SSD with the OS page cache warm. @@ -386,4 +414,4 @@ Criterion writes HTML reports to `target/criterion/`. A benchmark result should - Results are measurements, not service-level guarantees. - The full suite intentionally includes expensive large-fixture and quadratic workloads; run focused groups during development and the complete suite for a release-level performance review. -- The Criterion snapshots do not include heap or RSS; the performance envelope reports RSS from `/proc` (Linux only). The weekly soak test (#392) also records RSS, file size, and open and checkpoint time at 10M facts. +- Criterion does not collect heap or RSS itself. The #183 snapshot adds a process-wide RSS high-water mark from `/usr/bin/time` and separate engine-meter peaks; the performance envelope reports RSS from `/proc` (Linux only). The weekly soak test (#392) also records RSS, file size, and open and checkpoint time at 10M facts. diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index b8db655df5..aa12710c10 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -144,6 +144,8 @@ with no `CodedError` anywhere in its chain. | PRS-121 | Unterminated set literal | Parser | | PRS-122 | collect-set without a binding | Parser | | PRS-123 | collect-set operand is not a variable and an attribute | Parser | +| PRS-124 | Malformed `:rows` frame | Parser | +| PRS-125 | Position function with an explicit `:rows` frame | Parser | | QRY-001 | Invalid entity | Query Execution | | QRY-002 | Attribute must be a keyword | Query Execution | | QRY-003 | Cannot transact a pseudo-attribute | Query Execution | @@ -939,10 +941,10 @@ See the [Datalog Reference](https://project-minigraf.github.io/minigraf-docs/lat **Error text**: `unknown option in ':over' clause: '{}'` -**Cause**: An unrecognised keyword appeared inside the `:over` list. Valid options are `:order-by` and `:partition-by`. +**Cause**: An unrecognised keyword appeared inside the `:over` list. Valid options are `:order-by`, `:partition-by`, `:asc`, `:desc`, and (from v3.next) `:rows N preceding`. **Resolution**: -- Use only `:order-by` and `:partition-by`. +- Use `:order-by`, `:partition-by`, `:asc`, `:desc`, or `:rows N preceding` (from v3.next). - See the [Datalog Reference — Window Functions](https://project-minigraf.github.io/minigraf-docs/latest/datalog-reference/#window-functions). **Example**: @@ -2305,6 +2307,29 @@ with `PRS-047`. --- +### PRS-124 Malformed `:rows` frame + +**Error text**: `:rows requires one non-negative integer followed by preceding, and may appear only once` + +**Cause**: `:rows` inside `:over` lacks a literal non-negative integer or the lowercase plain symbol `preceding`, or appears twice. A logic variable and a prepared bind slot cannot supply the frame width. + +**Resolution**: +- Write `:rows 2 preceding` for the current row and up to two earlier rows. +- Use `:rows 0 preceding` for only the current row. + +--- + +### PRS-125 Position function with an explicit `:rows` frame + +**Error text**: `{} does not accept an explicit :rows frame` + +**Cause**: `rank`, `row-number`, `lag`, and `lead` operate on row positions or peers rather than an aggregate frame. + +**Resolution**: +- Remove `:rows` from these functions' `:over` list. Use `:rows` with `sum`, `count`, `min`, `max`, `avg`, or a registered aggregate. + +--- + ## QRY — Query Execution Errors Query execution errors occur after parsing succeeds, during pattern matching, diff --git a/docs/GRAMMAR.md b/docs/GRAMMAR.md index 95128b0c7f..2df37160b3 100644 --- a/docs/GRAMMAR.md +++ b/docs/GRAMMAR.md @@ -23,6 +23,7 @@ kw-limit ::= ":limit" (* not followed by word-cont *) (* token *) kw-offset ::= ":offset" (* not followed by word-cont *) (* token *) kw-distinct ::= ":distinct" (* not followed by word-cont *) (* token *) kw-over ::= ":over" (* not followed by word-cont *) (* token *) +kw-rows ::= ":rows" (* not followed by word-cont *) (* token *) kw-partition-by ::= ":partition-by" (* not followed by word-cont *) (* token *) kw-order-by ::= ":order-by" (* not followed by word-cont *) (* token *) kw-desc ::= ":desc" (* not followed by word-cont *) (* token *) @@ -83,12 +84,14 @@ query-section ::= find-section | where-section | as-of-section | valid-at-sectio | order-by-section | distinct-section (* ── FIND SECTION ── *) -find-section ::= kw-find find-spec+ -find-spec ::= window-expr | aggregate-expr | variable -aggregate-expr ::= "(" (op-sym | plain-sym) variable ")" -window-expr ::= "(" (op-sym | plain-sym) (variable kw-over | kw-over) over-clause ")" -over-clause ::= "(" over-option* ")" -over-option ::= kw-partition-by variable | kw-order-by variable | kw-desc | kw-asc +find-section ::= kw-find find-spec+ +find-spec ::= window-expr | aggregate-expr | variable +aggregate-expr ::= "(" (op-sym | plain-sym) variable ")" +window-expr ::= "(" (op-sym | plain-sym) (variable kw-over | kw-over) over-clause ")" +over-clause ::= "(" over-plain-option* (row-frame over-plain-option*)? ")" +over-plain-option ::= kw-partition-by variable | kw-order-by variable | kw-desc | kw-asc +row-frame ::= kw-rows frame-width "preceding" (* not followed by word-cont *) +frame-width ::= ("-" "0"+ | digit+) (* not followed by "." digit *) (* token *) (* ── WHERE SECTION ── *) where-section ::= kw-where where-clause+ diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 1cbd4acf08..aab85dadd0 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,11 +4,13 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Passing** | 1,873 | 1,904 | -| **Ignored** | 14 | 15 | -| **Total** | 1,887 | 1,919 | +| **Passing** | 1,885 | 1,917 | +| **Ignored** | 15 | 16 | +| **Total** | 1,900 | 1,933 | -**Verified**: 2026-10-26 with `cargo test --quiet` (and `--features test-hooks`). +**Verified**: 2026-10-27 with `cargo test --quiet` (and `--features test-hooks`) on the designated bench machine. + +#183 adds bounded row-frame parser, evaluator, and integration tests; one additional plan-independence case runs with `test-hooks`, including duplicate tie keys and NaN. A sliding-sum test checks recovery after integer saturation. Grammar corpus cases cover frame spellings and rejection. A meter test checks that a zero-width min frame reserves one deque slot. An ignored bench-machine diagnostic reproduces the Criterion datasets and prints the engine meter's peak for every measured case. #493 (`:distinct`) adds 18 tests with default features and one more with `test-hooks`. @@ -22,6 +24,8 @@ Not counted above: the browser tests and the WASI run (see [Browser and WASI](#b ## Covered Areas +- **Bounded row frames** (`tests/window_functions_test.rs`, `src/query/datalog/aggregate/tests.rs`, #183): `:rows N preceding` parsing and errors, physical rows with tied order keys, partition reset, descending order, width zero and maximum, all five built-in aggregates against a replay oracle with numeric edge cases, UDFs through prepared queries and cursors, grouping with `:with`, distinct output, memory-limit refusal for long min/max strings, and final `:order-by` matching. A `test-hooks` case checks answer bags with clause reordering on and off. + - **Optional distinct output** (`tests/distinct_test.rs`, #493): bag defaults, whole tuples, section syntax, cross-batch and committed/pending values, chunked write transactions, prepared execute/cursors, joins/rules/disjunction, aggregates and hidden `:with` groups, window peers and partitioned row numbers, temporal filters, typed equality and canonical float/set output, memory limits (including retained set payloads) and cursor cleanup. A meter unit test verifies each cell/key/value estimate includes set elements and their strings. With `test-hooks`, checks both reorder settings and hashed/correlated subplans. An engine unit test checks counters and state release. - **Core database behavior**: in-memory and file-backed operation, transactions, checkpoints, retractions, bi-temporal queries, recursive rules, prepared statements, aggregation, expressions, disjunction, window functions, UDFs, and magic-sets evaluation. @@ -378,7 +382,7 @@ These tests compare the database against an independent answer rather than a sin - Parser (3 unit tests), prepared slots (3 unit tests), `prs_115_…` in `tests/error_codes_prs_test.rs`, the grammar corpus (3 valid, 2 syntax, 2 semantic files) and two verifier `SEMANTIC` witnesses (`INT-012`, `PRS-115`). - `tests/limit_order_test.rs` (7 more tests, `test-hooks`): 14 ordered shapes (each `:limit` shape with an `:order-by` over plain, aggregate and window elements, ascending and descending, with ties), in memory and over committed and pending facts, with no option, limits 0, 1, 3 and the answer size, each with offsets 1, the answer size less one and two past it, and `:offset 2` alone: through `execute` and a cursor pulled one row at a time, and the limited ones through a prepared `:offset $o :limit $n` and its cursor, with reordering on and off, each returns the test's own full sort of the unlimited answer, sliced. Pages of three cover the ordered answer; every value class in one column ascending and descending (an integer before an equal float, `-0.0` before `0.0`); a write transaction's staged facts; `:offset` slot errors; a full sort over `query_memory_limit` is `QRY-012`, top-k under the same limit is not. - `src/query/engine/sort.rs` (7 unit tests): a full sort and top-k (k = 1 to past the input) equal a reference sort, ascending and descending, ties to the next column; `keep 0` pulls nothing; top-k's peak meter bytes are the same for 1,000 and 100,001 rows; `QRY-012` with and without `keep`; `rewind`. `src/query/engine/tests.rs` (1 test): top-k over 20,000 committed entities runs under a 512 KiB limit a full sort exceeds (the DICT lookups are dropped per batch). - - `src/query/datalog/aggregate/tests.rs` (2 tests, `row_order`), parser (4 unit tests: entries, directions, section orders, every `PRS-116`–`118`, `INT-012`/`013` and `PRS-115` case of `:offset`/`:order-by`), prepared `:offset` slots (1 unit test), `prs_116_…`–`prs_118_…` in `tests/error_codes_prs_test.rs`, the grammar corpus (4 valid, 3 syntax, 4 semantic files) and three verifier `SEMANTIC` witnesses (`PRS-116`–`118`); the verifier has 37 tokens and 16 templates. + - `src/query/datalog/aggregate/tests.rs` (2 tests, `row_order`), parser (4 unit tests: entries, directions, section orders, every `PRS-116`–`118`, `INT-012`/`013` and `PRS-115` case of `:offset`/`:order-by`), prepared `:offset` slots (1 unit test), `prs_116_…`–`prs_118_…` in `tests/error_codes_prs_test.rs`, the grammar corpus (4 valid, 3 syntax, 4 semantic fixtures added by #306) and three verifier `SEMANTIC` witnesses (`PRS-116`–`118`); the verifier now has 40 tokens and 17 templates. - **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. diff --git a/docs/benchmarks/183-row-frames.csv b/docs/benchmarks/183-row-frames.csv new file mode 100644 index 0000000000..2f50c035dd --- /dev/null +++ b/docs/benchmarks/183-row-frames.csv @@ -0,0 +1,129 @@ +rows,shape,function,frame,samples,median_ms,min_ms,max_ms,meter_peak_bytes +10000,hundred,avg,default,10,38.216,38.047,45.435,2880032 +10000,hundred,avg,half,10,37.971,37.709,38.306,2880032 +10000,hundred,avg,prefix,10,37.946,37.548,38.107,2880032 +10000,hundred,avg,sqrt,10,38.028,37.898,38.353,2880032 +10000,hundred,avg,two,10,38.014,37.949,39.824,2880032 +10000,hundred,avg,zero,10,38.141,37.929,39.37,2880032 +10000,hundred,count,default,10,36.714,36.383,39.914,2880032 +10000,hundred,count,half,10,36.429,36.27,36.58,2880032 +10000,hundred,count,prefix,10,36.579,36.476,43.759,2880032 +10000,hundred,count,sqrt,10,36.372,36.218,36.689,2880032 +10000,hundred,count,two,10,36.442,36.227,36.719,2880032 +10000,hundred,count,zero,10,36.683,36.314,38.303,2880032 +10000,hundred,frame_bench_sum,half,10,41.717,41.512,42.074,2880032 +10000,hundred,frame_bench_sum,two,10,38.786,38.584,39.961,2880032 +10000,hundred,frame_bench_sum,zero,10,38.478,38.269,45.598,2880032 +10000,hundred,max,default,10,36.893,36.713,37.324,2880032 +10000,hundred,max,half,10,36.683,36.496,36.827,2880440 +10000,hundred,max,prefix,10,36.773,36.556,37.452,2880832 +10000,hundred,max,sqrt,10,36.702,36.611,36.984,2880120 +10000,hundred,max,two,10,36.751,36.569,36.998,2880056 +10000,hundred,max,zero,10,36.814,36.497,38.497,2880040 +10000,hundred,min,default,10,37.003,36.693,37.332,2880032 +10000,hundred,min,half,10,36.762,36.582,38.357,2880440 +10000,hundred,min,prefix,10,36.715,36.592,37.018,2880832 +10000,hundred,min,sqrt,10,36.841,36.588,37.208,2880120 +10000,hundred,min,two,10,36.792,36.546,36.901,2880056 +10000,hundred,min,zero,10,37.642,36.798,42.014,2880040 +10000,hundred,sum,default,10,36.74,36.41,37.038,2880032 +10000,hundred,sum,half,10,36.436,36.281,36.87,2880032 +10000,hundred,sum,prefix,10,36.562,36.313,43.654,2880032 +10000,hundred,sum,sqrt,10,36.45,36.255,36.846,2880032 +10000,hundred,sum,two,10,36.445,36.341,36.571,2880032 +10000,hundred,sum,zero,10,36.456,36.327,38.216,2880032 +10000,one,avg,default,10,37.313,37.141,37.561,2560032 +10000,one,avg,half,10,37.891,37.423,39.122,2560032 +10000,one,avg,prefix,10,37.537,37.32,37.869,2560032 +10000,one,avg,sqrt,10,37.557,37.252,38.028,2560032 +10000,one,avg,two,10,37.543,37.261,44.691,2560032 +10000,one,avg,zero,10,37.401,37.214,38.014,2560032 +10000,one,count,default,10,35.979,35.828,36.148,2560032 +10000,one,count,half,10,35.956,35.665,37.577,2560032 +10000,one,count,prefix,10,35.915,35.628,36.423,2560032 +10000,one,count,sqrt,10,35.986,35.718,37.809,2560032 +10000,one,count,two,10,35.845,35.637,36.098,2560032 +10000,one,count,zero,10,35.919,35.751,43.166,2560032 +10000,one,frame_bench_sum,half,10,611.494,610.862,619.895,2560032 +10000,one,frame_bench_sum,two,10,38.275,38.059,38.648,2560032 +10000,one,frame_bench_sum,zero,10,38.152,37.911,38.425,2560032 +10000,one,max,default,10,36.076,35.989,36.385,2560032 +10000,one,max,half,10,36.044,35.833,37.944,2600040 +10000,one,max,prefix,10,36.052,35.846,36.246,2640032 +10000,one,max,sqrt,10,36.03,35.84,36.494,2560840 +10000,one,max,two,10,36.448,35.945,43.079,2560056 +10000,one,max,zero,10,36.033,35.88,36.261,2560040 +10000,one,min,default,10,36.055,35.977,36.347,2560032 +10000,one,min,half,10,36.198,35.933,37.096,2600040 +10000,one,min,prefix,10,36.022,35.834,36.187,2640032 +10000,one,min,sqrt,10,35.958,35.782,36.058,2560840 +10000,one,min,two,10,36.033,35.821,36.254,2560056 +10000,one,min,zero,10,36.024,35.829,36.066,2560040 +10000,one,sum,default,10,35.031,34.857,35.349,2560032 +10000,one,sum,half,10,35.972,35.763,36.163,2560032 +10000,one,sum,prefix,10,35.976,35.844,36.232,2560032 +10000,one,sum,sqrt,10,36.2,35.789,37.386,2560032 +10000,one,sum,two,10,35.988,35.696,36.103,2560032 +10000,one,sum,zero,10,35.983,35.782,43.11,2560032 +100000,hundred,avg,default,10,481.974,480.36,488.009,28800032 +100000,hundred,avg,half,10,485.477,482.38,497.196,28800032 +100000,hundred,avg,prefix,10,480.368,479.291,490.452,28800032 +100000,hundred,avg,sqrt,10,480.37,478.178,487.944,28800032 +100000,hundred,avg,two,10,480.703,478.221,522.269,28800032 +100000,hundred,avg,zero,10,481.393,478.93,490.49,28800032 +100000,hundred,count,default,10,468.277,465.909,518.257,28800032 +100000,hundred,count,half,10,468.864,465.886,481.361,28800032 +100000,hundred,count,prefix,10,466.271,465.249,478.569,28800032 +100000,hundred,count,sqrt,10,466.218,463.857,475.193,28800032 +100000,hundred,count,two,10,465.345,464.56,472.081,28800032 +100000,hundred,count,zero,10,466.301,465.065,472.213,28800032 +100000,hundred,frame_bench_sum,prefix,10,467.106,466.312,475.958,28800032 +100000,hundred,max,default,10,468.759,466.824,476.002,28800032 +100000,hundred,max,half,10,467.439,466.269,474.732,28804040 +100000,hundred,max,prefix,10,467.983,465.328,491.99,28808032 +100000,hundred,max,sqrt,10,467.135,465.908,520.172,28800288 +100000,hundred,max,two,10,467.562,465.362,487.448,28800056 +100000,hundred,max,zero,10,467.299,465.093,474.135,28800040 +100000,hundred,min,default,10,470.129,468.459,477.493,28800032 +100000,hundred,min,half,10,467.842,465.288,517.53,28804040 +100000,hundred,min,prefix,10,467.082,464.12,477.521,28808032 +100000,hundred,min,sqrt,10,466.178,465.038,487.976,28800288 +100000,hundred,min,two,10,466.175,465.336,472.673,28800056 +100000,hundred,min,zero,10,467.469,465.302,473.46,28800040 +100000,hundred,sum,default,10,467.42,466.103,479.282,28800032 +100000,hundred,sum,half,10,468.567,465.436,536.4,28800032 +100000,hundred,sum,prefix,10,468.472,466.837,496.627,28800032 +100000,hundred,sum,sqrt,10,466.975,465.878,473.019,28800032 +100000,hundred,sum,two,10,469.596,466.401,475.842,28800032 +100000,hundred,sum,zero,10,467.423,465.993,516.796,28800032 +100000,one,avg,default,10,472.672,471.09,480.82,25600032 +100000,one,avg,half,10,476.327,473.074,481.878,25600032 +100000,one,avg,prefix,10,474.807,472.973,483.441,25600032 +100000,one,avg,sqrt,10,471.985,469.837,525.068,25600032 +100000,one,avg,two,10,471.792,470.666,482.456,25600032 +100000,one,avg,zero,10,470.526,469.375,481.347,25600032 +100000,one,count,default,10,461.12,459.123,513.727,25600032 +100000,one,count,half,10,458.763,457.626,467.517,25600032 +100000,one,count,prefix,10,455.391,453.441,505.226,25600032 +100000,one,count,sqrt,10,459.737,456.223,465.222,25600032 +100000,one,count,two,10,458.868,456.833,465.577,25600032 +100000,one,count,zero,10,460.301,457.774,470.014,25600032 +100000,one,frame_bench_sum,prefix,10,459.714,456.581,469.913,25600032 +100000,one,max,default,10,459.24,458.501,470.535,25600032 +100000,one,max,half,10,459.465,456.782,519.54,26000040 +100000,one,max,prefix,10,458.934,456.345,472.132,26400032 +100000,one,max,sqrt,10,459.102,457.063,467.831,25602568 +100000,one,max,two,10,458.487,457.2,472.298,25600056 +100000,one,max,zero,10,457.778,456.301,468.98,25600040 +100000,one,min,default,10,457.663,456.568,472.008,25600032 +100000,one,min,half,10,462.152,461.095,516.54,26000040 +100000,one,min,prefix,10,462.249,459.854,473.246,26400032 +100000,one,min,sqrt,10,457.975,457.28,464.844,25602568 +100000,one,min,two,10,459.229,457.254,468.617,25600056 +100000,one,min,zero,10,460.195,458.793,470.344,25600040 +100000,one,sum,default,10,457.866,456.74,511.362,25600032 +100000,one,sum,half,10,460.918,459.94,469.264,25600032 +100000,one,sum,prefix,10,457.421,455.981,465.981,25600032 +100000,one,sum,sqrt,10,461.163,459.67,469.551,25600032 +100000,one,sum,two,10,461.745,459.065,477.869,25600032 +100000,one,sum,zero,10,459.792,458.688,468.106,25600032 diff --git a/docs/superpowers/plans/2026-10-27-183-row-frames.md b/docs/superpowers/plans/2026-10-27-183-row-frames.md new file mode 100644 index 0000000000..baa7efd209 --- /dev/null +++ b/docs/superpowers/plans/2026-10-27-183-row-frames.md @@ -0,0 +1,18 @@ +# #183 Bounded sliding row frames — implementation plan + +Status: approved by Claude and maintainer after three design reviews. Follow `docs/superpowers/specs/2026-10-27-183-row-frames-design.md`. The maintainer approved implementation on 2026-10-27. + +Baseline: `origin/v3` at `82e32c47` passed `cargo test --quiet` on the idle designated bench machine on 2026-10-26. The temporary remote worktree was removed; the preexisting shared Cargo target cache was reused. + +Implementation was rebased onto `origin/v3` at `f549245f4` after #765's window scratch-memory fix merged. The bounded evaluator uses #765's charged partition index and scratch guard. + +1. Work in the already-created ignored `.worktrees/183-row-frames` worktree on `feat/183-row-frames`, based on `origin/v3`. Keep `main` untouched. Before code changes, read `superpowers:test-driven-development`; before completion, read `superpowers:verification-before-completion`. +2. Add parser/AST tests first: `N=0`, `2`, `i64::MAX`, option order, `-0`, duplicates, missing/wrong suffix, negative/float/variable/bind-slot counts, and position functions with an explicit frame. Check rejection of split tokens `+2`, `2N`, `2M` and lexer overflow beyond `i64::MAX`. Confirm default-frame parsing still passes. A new AST-field assertion can make the first red run fail to compile; otherwise only new framed-syntax expectations should fail. +3. Add `WindowFrame` and `WindowSpec.frame` in the private AST, parse `:rows`, and register two fresh PRS errors after checking the current registry and open branches for collisions. Update `docs/ERROR_REFERENCE.md` and `tests/grammar/grammar.pest`; run the parser verifier. Include equality tests showing two otherwise identical window expressions with different frames stay distinct in final `:order-by` matching. +4. Add integration tests before evaluator changes: physical-row frames with ties; first/last row, empty/singleton partitions and resets; descending order; nil/non-numeric values; all five built-ins and a UDF; grouped input, including `:with`; direct, prepared, and cursor queries across page boundaries; distinct/limit/offset; and memory-limit refusal, including large strings in min/max. Add a small replay oracle with generated partitions, ties, N values, numeric edge cases (NaN payloads, infinities, signed zero, mixed ints/floats, saturation), nils, and directions. Add a `test-hooks` plan-independence case comparing answer bags with reordering on/off. The red run should fail framed-result assertions while existing default-frame tests remain green. +5. Implement the shared `aggregate::windows` bounded path. Preserve default peer handling and lag/lead. Use reversible exact sliding state for count/sum/avg, monotonic index deques for min/max, replay for middle-sized UDF frames, and an O(R) cumulative path when N covers the whole prefix. Charge retained deque capacity and every result payload to `WindowColumnMeter`; retain no more than one UDF accumulator. Use checked/saturating conversion for 32-bit targets. The replay oracle must match built-in results bit-for-bit where floats are involved. +6. Verify on the designated bench machine first: focused `cargo test --test window_functions_test`, parser/aggregate unit tests, `cargo test --features test-hooks`, `cargo test --quiet`, `cargo clippy --all-features -- -D warnings`, and the two wasm clippy targets (`wasm32-unknown-unknown --features browser` and `wasm32-wasip1`). Run `cargo fmt -- --check` locally because it is light. Run WASI tests with the project's configured runner when installed; otherwise rely on the wasm CI gate and say so. Run no heavy local cargo command unless the bench machine is unreachable or busy, and report that fallback. Confirm all CI-required commands rather than repeating optional tests. +7. Commit a reproducible benchmark harness using the existing Criterion dev-dependency for framed sum/count/min/max/avg plus one UDF. On an otherwise idle bench machine, pin timing runs with `numactl` to one NUMA node and keep builds/tests out of the timing interval. For built-ins, use one partition and many equal-sized partitions, with total R=10,000 and 100,000 rows. Set N=0, 2, about √P, P/2, and at least P, where P is the partition length in each case. Warm each case and record at least five measured runs with median, range, and peak engine-meter bytes (the ignored `window_rows_benchmark_meter_peaks` diagnostic reproduces the datasets); record peak RSS where available. Compare built-ins to the same dataset's default frame. The built-in gate is median ≤5× the default at R=100,000 for each N, with no more than 15× growth from R=10,000 at comparable partition shape. If a gate fails, revise the algorithm and spec, obtain another Claude design review, and rerun the gate. For UDFs, measure R=10,000 with N=0, 2, and P/2, plus R=100,000 with N≥P to exercise the linear prefix path; report absolute times and callback counts. Do not run the quadratic R=100,000/P/2 UDF case. UDF middle-sized frames retain documented replay complexity. Discard timings from a busy machine. +8. After every remote test/benchmark run, remove only the scratch worktree, temporary target/fixture/run directories, and scripts that run created. Report what was kept and why. Reuse existing build caches deliberately; do not leave new scratch files behind. +9. Update repo docs and the docs-site Datalog reference with version-scoped text. Cross-check ROADMAP.md, README.md, CLAUDE.md, CHANGELOG.md, and docs/TEST_COVERAGE.md; update each affected status or inventory without calling the unreleased feature published. Make the docs-site change a separate PR, version-scoped so it does not prematurely claim a released version. No version bump or tag in this feature PR. +10. Apply verification-before-completion, inspect the diff and all required outputs, request Claude's independent final code review before opening the core PR, and verify every finding before acting. Open the core PR against `v3` as a draft only after that review; hold its merge until after the v3.0.0 cut, so #183 ships in v3.next. Do not merge without the user's explicit direction. diff --git a/docs/superpowers/specs/2026-10-27-183-row-frames-design.md b/docs/superpowers/specs/2026-10-27-183-row-frames-design.md new file mode 100644 index 0000000000..19cd67d140 --- /dev/null +++ b/docs/superpowers/specs/2026-10-27-183-row-frames-design.md @@ -0,0 +1,37 @@ +# #183 Bounded sliding row frames — design + +Date: 2026-10-27. Target: v3.next, based on current `origin/v3` (after #182 and #765). The PR against `v3` stays draft and must not merge before the v3.0.0 cut. Status: approved by Claude and maintainer after three design reviews. + +## Goal and philosophy + +Add `:rows N preceding` to Datalog window aggregates without changing stored data or the default frame. This is an additive, in-process query feature for ordered temporal/event data. No new dependency, configuration, service, file-format change, or public API break. Keep the implementation shared by all query entry points and covered by correctness, memory-budget, and performance checks. + +## Language and semantics + +Example: `(sum ?amount :over (:partition-by ?account :order-by ?time :rows 2 preceding))`. + +`N` is a literal, nonnegative EDN integer in `0..=i64::MAX`. `preceding` is the plain symbol after it. The existing lexer also splits adjacent `2preceding` into the integer and symbol, so the grammar corpus accepts that spelling. Exactly one `:rows` option is accepted per `:over` list. Option order follows the existing flexible `:over` parser; `:order-by` remains required. `N=0` means current row only; `N=2` means up to two earlier physical rows plus current row. At a partition start the frame truncates. At a partition boundary it resets. `N` greater than partition length includes the whole prefix. No following/current-row/range frame syntax in this issue. + +The row order is the existing window total order: `:order-by` value and direction, then the values of all variables named by plain `:find` elements and window arguments/partition/order keys in `:find` order, then input position. `aggregate::named_vars` includes the argument and keys of *every* window in the `:find`. The existing `value_order` breaks numeric ties: integer 1 precedes float 1.0, -0.0 precedes 0.0, and distinct NaN bit patterns have a defined order; other value classes are also totally ordered. An `Equal` comparison of all named-variable keys therefore does not hide distinct typed/bitwise values used by a window. In a grouped query, the parser requires every window variable to be a plain grouping variable, and the engine does not add `:with` keys when a window is present. Thus two rows tied through every named-variable key have the same visible plain columns and same input to every window. Swapping such rows may change which physical row gets a position but cannot change the answer bag. Keep that plan-independence guarantee and test it with optimizer reordering enabled and disabled, including integer/float, signed-zero, and NaN cases. Query results retain bag multiplicity until an explicit `:distinct`. + +Peers with the same order key are separate positions for an explicit `:rows` frame, so they can have different results. An absent `:rows` retains the current default: an unbounded preceding frame ending at the *last peer* of the current row; all peers share the aggregate result. The existing window functions are exactly `sum`, `count`, `min`, `max`, `avg`, `rank`, `row-number`, `lag`, `lead`, and registered aggregate UDFs. `rank`, `row-number`, `lag`, and `lead` retain their current behavior when no frame is specified and reject an explicit frame because it does not define their output. This also prevents silently ignored options. The five built-in aggregates and registered aggregate UDFs accept `:rows`; `count-distinct` and `sum-distinct` remain rejected with PRS-031. An unknown UDF name is rejected at execution with the existing QRY-011, including when a query was prepared first. + +The frame includes nil and nonnumeric values as rows. Existing function-specific stepping remains unchanged: count skips nil and returns 0 when none remain; sum skips nonnumbers and returns integer 0 when none remain; avg skips nonnumbers and returns nil when none remain; min/max skip nil and return nil when none remain; UDFs receive each value including nil. Aggregation still precedes windows in grouped queries. `:distinct`, final ordering, offset/limit and cursors still operate after window values are computed over all eligible rows. + +## AST and parser + +Add `WindowFrame` (initially `RowsPreceding(u64)`) and `frame: Option` to `WindowSpec`. `None` is the existing default. The lexer parses integers as `i64`; only a nonnegative `EdnValue::Integer` converts to `u64` in the AST. Parse `:rows` as exactly `Integer(N)` followed by lowercase plain symbol `preceding`; reject negative, float, missing, wrong suffix (including `:preceding` and case variants), duplicate, logic-variable, or bind-slot input with a new registered PRS code for malformed frame syntax. `-0` is accepted as zero because the existing lexer produces `Integer(0)`; `+2`, `2N`, and `2M` split into multiple tokens and fail frame validation with `PRS-124`; integers beyond `i64::MAX` fail in the lexer with `INT-008`. None are newly supported. Reject explicit frames on rank/row-number/lag/lead with a separate registered PRS code. These two codes are allocated after checking the current error registry and open branches. Add them to `docs/ERROR_REFERENCE.md` and the parser-verifier grammar. Existing accepted syntax and its errors remain unchanged; `:rows` was previously an unknown `:over` option (PRS-039), so its new malformed/unsupported errors are intentional. + +`WindowSpec`, `WindowFrame`, and `ErrorCode` are behind private crate modules and are not part of the exported Rust API. The new AST field needs updates to internal struct literals. `FindSpec::display_name` is a column label, not a round-trip representation or query cache key; existing window labels omit `:over` details, and results/cursors are positional. `PreparedQuery` stores the parsed query directly; `Cursor` owns an already opened query and snapshot, with no query fingerprint. There is no normalized-AST cache or persisted rule/query form. Check final `:order-by` matching between otherwise identical window expressions with different frames, since it uses `FindSpec` equality. + +## Evaluation + +Extend the shared `aggregate::windows` calculation used by the engine; no second implementation. Retain the existing partition sort and output-to-input-row mapping. After #765 merges, partitions are slices of one charged sorted row-index vector; evaluate each bounded frame within its slice so it resets at the partition boundary. An explicit frame at sorted position `p` covers positions `p.saturating_sub(N)..=p`, with safe conversion on 32-bit targets. Keep `None` on the current peer-group path and lag/lead on their row-offset path. Keep the #765 `WindowColumnMeter` accounting for every result value, including strings/sets. + +For the five built-in aggregates, maintain a sliding state as rows enter and leave the frame, giving O(R) evaluation per partition after sorting. `count` uses a non-nil count. Current `Running::Sum`/`Avg` already use `Sum`: an `i128` integer total plus a fixed-limb exact finite-float sum, rounded once at output. Extend that representation with reversible counters for NaNs, infinities, float presence, and signed zero; removal must be bit-for-bit equivalent to replaying the frame in existing `Running` semantics, including mixed numeric types and overflow saturation only at output. `min`/`max` use monotonic deques of row indices under the existing total value order, skipping nil; the deque must return the same typed/bitwise value as `Running::Extreme` for mixed values and NaNs. Reserve at most `min(partition length, N+1)` indices and charge their actual capacity to the window memory meter. Do not replace exact sums with rounded subtraction. + +Registered aggregate UDFs have no inverse or merge API, so replay the current frame with a fresh accumulator for each row: O(R * min(N+1, R)) steps. When N covers the whole partition prefix, use one running accumulator and emit each row's value in O(R), including for UDFs; `Udf::value(&self)` already finalizes without consuming the accumulator. A middle-sized UDF frame on a large partition can cause billions of callbacks; there is no separate CPU step budget or cancellation check in this window loop, and the query memory limit does not prevent that cost. Document this clearly in the Datalog reference. A fresh UDF accumulator may allocate arbitrary memory outside the engine meter, as it already can for a default window; retain only one at a time and document this existing limit. A built-in sum holds constant-sized exact state; a deque holds at most R indices, and result payloads retain their #765 charging. The benchmark harness uses existing Criterion dev-dependency, so no new dependency is needed. The plan's timing gate covers small, middle, and large N for built-ins; any change of algorithm after a failed gate requires a spec revision and renewed review. + +## Coverage and docs + +Tests: parse/AST accepted `0`, `2`, huge N and option order; malformed forms and nonaggregates; first/last rows, one-row/empty partitions, partition reset, ascending/descending, tied keys with deterministic tie-break, nil/non-numeric values, all five built-ins and a UDF, grouped queries, prepared/cursor paging and final limit/distinct interaction, engine memory limit including large min/max strings. Assert default peer behavior is unchanged. Compare optimized built-ins with a simple replay oracle across generated partitions, ties, N values, nils, mixed numeric values and directions. Compare full result bags with optimizer reordering on/off. If `WindowSpec` is constructed directly in tests, update every constructor. Update grammar verifier, Datalog reference (current docs-site checkout), version annotations, error reference, ROADMAP, and coverage inventory as relevant. No release tag or version bump in this feature PR. diff --git a/src/error.rs b/src/error.rs index c1a4376fcd..3760971bde 100644 --- a/src/error.rs +++ b/src/error.rs @@ -173,6 +173,8 @@ pub(crate) enum ErrorCode { Prs121, Prs122, Prs123, + Prs124, + Prs125, Qry001, Qry002, Qry003, @@ -1083,6 +1085,18 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "collect-set takes a ?variable and an attribute keyword; got {}", ErrorCategory::Parser, ), + ( + ErrorCode::Prs124, + "PRS-124", + ":rows requires one non-negative integer followed by preceding, and may appear only once", + ErrorCategory::Parser, + ), + ( + ErrorCode::Prs125, + "PRS-125", + "{} does not accept an explicit :rows frame", + ErrorCategory::Parser, + ), ( ErrorCode::Qry001, "QRY-001", @@ -2393,6 +2407,8 @@ mod tests { | ErrorCode::Prs121 | ErrorCode::Prs122 | ErrorCode::Prs123 + | ErrorCode::Prs124 + | ErrorCode::Prs125 | ErrorCode::Qry001 | ErrorCode::Qry002 | ErrorCode::Qry003 @@ -2670,6 +2686,8 @@ mod tests { ErrorCode::Prs121, ErrorCode::Prs122, ErrorCode::Prs123, + ErrorCode::Prs124, + ErrorCode::Prs125, ErrorCode::Qry001, ErrorCode::Qry002, ErrorCode::Qry003, diff --git a/src/query/datalog/aggregate.rs b/src/query/datalog/aggregate.rs index c02cf8fff6..8e5c6619fb 100644 --- a/src/query/datalog/aggregate.rs +++ b/src/query/datalog/aggregate.rs @@ -3,14 +3,14 @@ //! does not depend on the order of its input. use super::functions::{AggImpl, Builtin, FunctionRegistry, UdfError, UdfFinaliseFn, UdfStepFn}; -use super::types::{FindSpec, Order, WindowFunc, WindowSpec}; +use super::types::{FindSpec, Order, WindowFrame, WindowFunc, WindowSpec}; use crate::error::{ErrorCode, err_coded}; use crate::graph::types::Value; use anyhow::Result; use std::any::Any; use std::cmp::Ordering; use std::collections::TryReserveError; -use std::collections::{BTreeMap, BTreeSet}; +use std::collections::{BTreeMap, BTreeSet, VecDeque}; use std::mem::size_of; /// The class of a value in [`value_order`]: numbers, strings, booleans, @@ -336,6 +336,83 @@ impl Sum { } } +/// Reversible exact sum for a bounded row frame. The counters recover the +/// booleans in `Sum` when a value leaves the frame. +#[derive(Default)] +struct SlidingSum { + sum: Sum, + floats: u64, + nan: u64, + pos_inf: u64, + neg_inf: u64, + not_neg_zero: u64, +} + +impl SlidingSum { + fn add(&mut self, v: &Value) { + if !self.sum.add(v) { + return; + } + match v { + Value::Integer(_) => self.not_neg_zero += 1, + Value::Float(f) => { + self.floats += 1; + if f.is_nan() { + self.nan += 1; + } else if *f == f64::INFINITY { + self.pos_inf += 1; + } else if *f == f64::NEG_INFINITY { + self.neg_inf += 1; + } else if f.to_bits() != (-0.0f64).to_bits() { + self.not_neg_zero += 1; + } + } + _ => {} + } + } + + fn remove(&mut self, v: &Value) { + match v { + Value::Integer(i) => { + self.sum.ints -= i128::from(*i); + self.not_neg_zero -= 1; + } + Value::Float(f) => { + self.floats -= 1; + if f.is_nan() { + self.nan -= 1; + } else if *f == f64::INFINITY { + self.pos_inf -= 1; + } else if *f == f64::NEG_INFINITY { + self.neg_inf -= 1; + } else { + if f.to_bits() != (-0.0f64).to_bits() { + self.not_neg_zero -= 1; + } + if let Some(exact) = self.sum.floats.as_mut() { + exact.add_float(-*f); + } + } + } + _ => return, + } + self.sum.count -= 1; + self.sum.any_float = self.floats > 0; + self.sum.nan = self.nan > 0; + self.sum.pos_inf = self.pos_inf > 0; + self.sum.neg_inf = self.neg_inf > 0; + self.sum.not_neg_zero = self.not_neg_zero > 0; + } + + fn value(&self) -> Value { + self.sum.value() + } + + fn mean(&self) -> Value { + self.sum.mean() + } +} + /// `v` with `-0.0` as `0.0` and every NaN as one NaN, so equal values under /// `Value`'s `Ord` are stored alike. fn canonical(v: &Value) -> Value { @@ -828,6 +905,137 @@ pub(crate) fn windows( continue; } + if let Some(WindowFrame::RowsPreceding(n)) = &ws.frame { + let preceding = usize::try_from(*n).unwrap_or(usize::MAX); + let partition_read = + |pos: usize| partition.get(pos).map_or(&NULL, |&r| read(r, var)); + match &ws.func { + WindowFunc::Count => { + let mut count = 0i64; + for (pos, &row) in partition.iter().enumerate() { + if !matches!(read(row, var), Value::Null) { + count = count.saturating_add(1); + } + if pos > preceding + && !matches!(partition_read(pos - preceding - 1), Value::Null) + { + count -= 1; + } + store_window_value( + &mut values, + row, + &Value::Integer(count), + &mut bytes, + scratch.meter, + )?; + } + } + WindowFunc::Sum | WindowFunc::Avg => { + let mut sum = SlidingSum::default(); + for (pos, &row) in partition.iter().enumerate() { + sum.add(read(row, var)); + if pos > preceding { + sum.remove(partition_read(pos - preceding - 1)); + } + let result = if matches!(ws.func, WindowFunc::Sum) { + sum.value() + } else { + sum.mean() + }; + store_window_value( + &mut values, + row, + &result, + &mut bytes, + scratch.meter, + )?; + } + } + WindowFunc::Min | WindowFunc::Max => { + let max = matches!(ws.func, WindowFunc::Max); + // This guard releases the deque charge on every exit, + // including an output memory-limit error. + let capacity = partition.len().min(preceding.saturating_add(1)); + let planned = capacity.saturating_mul(size_of::()); + let mut deque_scratch = WindowScratch::new(&mut *scratch.meter, planned)?; + let mut deque = VecDeque::::new(); + deque_scratch.reserve(deque.try_reserve_exact(capacity))?; + let extra = deque + .capacity() + .saturating_sub(capacity) + .saturating_mul(size_of::()); + deque_scratch.meter.charge(extra)?; + deque_scratch.bytes = deque_scratch.bytes.saturating_add(extra); + for (pos, &row) in partition.iter().enumerate() { + let start = pos.saturating_sub(preceding); + while deque.front().is_some_and(|&front| front < start) { + deque.pop_front(); + } + let current = read(row, var); + if !matches!(current, Value::Null) { + while let Some(&back) = deque.back() { + let order = value_order(current, partition_read(back)); + if (max && order.is_gt()) || (!max && order.is_lt()) { + deque.pop_back(); + } else { + break; + } + } + deque.push_back(pos); + } + let source = + deque.front().map_or(&NULL, |&front| partition_read(front)); + store_window_value( + &mut values, + row, + source, + &mut bytes, + deque_scratch.meter, + )?; + } + } + WindowFunc::Udf(_) => { + let prefix = preceding >= partition.len().saturating_sub(1); + let mut running = if prefix { + Some(Running::new(ws, registry)?) + } else { + None + }; + for (pos, &row) in partition.iter().enumerate() { + let value = if let Some(acc) = running.as_mut() { + acc.step(read(row, var))?; + acc.value()? + } else { + let mut acc = Running::new(ws, registry)?; + for &r in partition + .get(pos.saturating_sub(preceding)..=pos) + .unwrap_or(&[]) + { + acc.step(read(r, var))?; + } + acc.value()? + }; + store_window_value( + &mut values, + row, + &value, + &mut bytes, + scratch.meter, + )?; + } + } + WindowFunc::Rank + | WindowFunc::RowNumber + | WindowFunc::Lag + | WindowFunc::Lead => { + // The parser rejects explicit frames for these functions. + return Err(err_coded!(ErrorCode::Int030, ws.func_name())); + } + } + offset = end; + continue; + } + let mut running = match ws.func { WindowFunc::Rank | WindowFunc::RowNumber => None, _ => Some(Running::new(ws, registry)?), @@ -879,6 +1087,22 @@ pub(crate) fn windows( Ok(out) } +/// Charge the payload before cloning a window result into its output row. +fn store_window_value( + values: &mut [Value], + row: usize, + source: &Value, + bytes: &mut usize, + meter: &mut impl WindowColumnMeter, +) -> Result<()> { + let payload = meter.charge_payload(source)?; + *bytes = bytes.saturating_add(payload); + if let Some(slot) = values.get_mut(row) { + *slot = source.clone(); + } + Ok(()) +} + /// The 1-based position `pos + 1` as an integer. fn position(pos: usize) -> Result { i64::try_from(pos + 1) diff --git a/src/query/datalog/aggregate/tests.rs b/src/query/datalog/aggregate/tests.rs index d83cbf6b19..6d7b9b895c 100644 --- a/src/query/datalog/aggregate/tests.rs +++ b/src/query/datalog/aggregate/tests.rs @@ -402,6 +402,139 @@ fn running_values() { ); } +#[test] +fn sliding_sum_matches_replay_with_numeric_edges() { + let values = [ + i(i64::MAX), + f(-0.0), + f(f64::INFINITY), + f(f64::NEG_INFINITY), + f(f64::from_bits(0x7ff8_0000_0000_0001)), + i(i64::MIN), + f(0.5), + Value::Null, + Value::String("skip".into()), + f(0.0), + ]; + let mut sliding = SlidingSum::default(); + for (pos, value) in values.iter().enumerate() { + sliding.add(value); + if let Some(expired) = pos.checked_sub(3) { + sliding.remove(&values[expired]); + } + let start = pos.saturating_sub(2); + let mut replay = Sum::default(); + for value in &values[start..=pos] { + replay.add(value); + } + for (actual, expected) in [ + (sliding.value(), replay.value()), + (sliding.mean(), replay.mean()), + ] { + match (actual, expected) { + (Value::Float(a), Value::Float(b)) => assert_eq!(a.to_bits(), b.to_bits()), + (a, b) => assert_eq!(a, b), + } + } + } +} + +#[test] +fn sliding_integer_sum_recovers_after_saturation() { + let values = [i(i64::MAX), i(i64::MAX), i(-5), i(1)]; + let mut sliding = SlidingSum::default(); + let expected = [i(i64::MAX), i(i64::MAX), i(i64::MAX - 5), i(-4)]; + for (pos, value) in values.iter().enumerate() { + sliding.add(value); + if let Some(expired) = pos.checked_sub(2) { + sliding.remove(&values[expired]); + } + assert_eq!(sliding.value(), expected[pos]); + let mut replay = Sum::default(); + for value in &values[pos.saturating_sub(1)..=pos] { + replay.add(value); + } + assert_eq!(sliding.value(), replay.value()); + } +} + +struct UnlimitedWindowMeter; + +impl WindowColumnMeter for UnlimitedWindowMeter { + fn charge(&mut self, _: usize) -> Result<()> { + Ok(()) + } + + fn uncharge(&mut self, _: usize) {} + + fn reserve( + &mut self, + result: std::result::Result<(), std::collections::TryReserveError>, + _: usize, + _: usize, + ) -> Result<()> { + result.map_err(|_| anyhow::anyhow!("reserve failed")) + } + + fn charge_payload(&mut self, _: &Value) -> Result { + Ok(0) + } +} + +#[test] +fn bounded_builtins_match_running_replay_for_every_row() { + let reg = FunctionRegistry::with_builtins(); + let data = [ + Value::Null, + Value::String("x".into()), + i(i64::MAX), + f(-0.0), + f(0.0), + f(f64::from_bits(0x7ff8_0000_0000_0001)), + f(f64::INFINITY), + i(-2), + f(f64::NEG_INFINITY), + kw(":tail"), + ]; + let rows: Vec> = data + .iter() + .enumerate() + .map(|(pos, v)| vec![v.clone(), i(i64::try_from(pos).expect("position"))]) + .collect(); + for func in ["sum", "count", "min", "max", "avg"] { + for width in [0, 1, 3, i64::MAX] { + for desc in [false, true] { + let direction = if desc { " :desc" } else { "" }; + let ws = window(&format!( + "({func} ?v :over (:order-by ?o{direction} :rows {width} preceding))" + )); + let mut meter = UnlimitedWindowMeter; + let columns = windows(&[FindSpec::Window(ws.clone())], &rows, ®, &mut meter) + .expect("bounded window"); + let actual = &columns[0].values; + let ordered: Vec<&Value> = if desc { + data.iter().rev().collect() + } else { + data.iter().collect() + }; + for (row, got) in actual.iter().enumerate() { + let pos = if desc { data.len() - row - 1 } else { row }; + let start = pos.saturating_sub(usize::try_from(width).unwrap_or(usize::MAX)); + let mut replay = Running::new(&ws, ®).expect("running"); + for value in &ordered[start..=pos] { + replay.step(value).expect("step"); + } + let expected = replay.value().expect("value"); + match (got, expected) { + (Value::Float(a), Value::Float(b)) => assert_eq!(a.to_bits(), b.to_bits()), + (got, expected) => assert_eq!(*got, expected), + } + } + } + } + } +} + #[test] fn named_vars_in_find_order() { let parse = |src: &str| match parse_datalog_command(src) { diff --git a/src/query/datalog/parser.rs b/src/query/datalog/parser.rs index ace892bbbe..104f0402f2 100644 --- a/src/query/datalog/parser.rs +++ b/src/query/datalog/parser.rs @@ -784,6 +784,7 @@ fn parse_window_expr(elems: &[EdnValue]) -> Result { let mut partition_by: Option = None; let mut order_by: Option = None; let mut order = Order::Asc; + let mut frame = None; let mut j = 0; while j < over_list.len() { @@ -816,6 +817,23 @@ fn parse_window_expr(elems: &[EdnValue]) -> Result { ":asc" => { order = Order::Asc; } + ":rows" => { + if frame.is_some() { + bail_coded!(ErrorCode::Prs124); + } + let n = match over_list.get(j + 1) { + Some(EdnValue::Integer(n)) if *n >= 0 => { + u64::try_from(*n).map_err(|_| err_coded!(ErrorCode::Prs124))? + } + _ => bail_coded!(ErrorCode::Prs124), + }; + if !matches!(over_list.get(j + 2), Some(EdnValue::Symbol(s)) if s == "preceding") + { + bail_coded!(ErrorCode::Prs124); + } + frame = Some(WindowFrame::RowsPreceding(n)); + j += 2; + } other => { bail_coded!(ErrorCode::Prs039, other); } @@ -829,6 +847,14 @@ fn parse_window_expr(elems: &[EdnValue]) -> Result { } let order_by = order_by.ok_or_else(|| err_coded!(ErrorCode::Prs084))?; + if frame.is_some() + && matches!( + func, + WindowFunc::Rank | WindowFunc::RowNumber | WindowFunc::Lag | WindowFunc::Lead + ) + { + bail_coded!(ErrorCode::Prs125, func_name); + } Ok(FindSpec::Window(WindowSpec { func, @@ -836,6 +862,7 @@ fn parse_window_expr(elems: &[EdnValue]) -> Result { partition_by, order_by, order, + frame, })) } @@ -4353,6 +4380,108 @@ mod window_parse_tests { } } + #[test] + fn parse_rows_preceding_frame_and_keep_default() { + let parse = |over: &str| { + let q = format!( + "(query [:find (sum ?v :over ({over})) :where [?e :score ?v] [?e :group ?g]])" + ); + match parse_datalog_command(&q).expect("query parses") { + DatalogCommand::Query(q) => match q.find.into_iter().next() { + Some(FindSpec::Window(ws)) => ws, + _ => panic!("expected window"), + }, + _ => panic!("expected query"), + } + }; + assert_eq!(parse(":order-by ?v").frame, None); + assert_eq!( + parse(":rows 0 preceding :order-by ?v").frame, + Some(WindowFrame::RowsPreceding(0)) + ); + assert_eq!( + parse(":order-by ?v :rows -0 preceding").frame, + Some(WindowFrame::RowsPreceding(0)) + ); + assert_eq!( + parse(":partition-by ?g :order-by ?v :rows 9223372036854775807 preceding").frame, + Some(WindowFrame::RowsPreceding( + u64::try_from(i64::MAX).expect("fits") + )) + ); + } + + #[test] + fn parse_rows_frame_rejects_malformed_and_position_functions() { + let code = |expr: &str| { + let q = format!("(query [:find {expr} :where [?e :score ?v]])"); + let error = match parse_datalog_command(&q) { + Ok(_) => panic!("frame must be rejected"), + Err(error) => error, + }; + crate::MinigrafError::from(error).code().to_string() + }; + for option in [ + ":rows -1 preceding", + ":rows 1.5 preceding", + ":rows ?v preceding", + ":rows $n preceding", + ":rows 2 :preceding", + ":rows 2 PRECEDING", + ":rows 2", + ":rows 1 preceding :rows 2 preceding", + ] { + assert_eq!( + code(&format!("(sum ?v :over (:order-by ?v {option}))")), + "PRS-124" + ); + } + for name in ["rank", "row-number"] { + assert_eq!( + code(&format!("({name} :over (:order-by ?v :rows 1 preceding))")), + "PRS-125" + ); + } + for name in ["lag", "lead"] { + assert_eq!( + code(&format!( + "({name} ?v :over (:order-by ?v :rows 1 preceding))" + )), + "PRS-125" + ); + } + for n in ["+2", "2N", "2M"] { + assert_eq!( + code(&format!( + "(sum ?v :over (:order-by ?v :rows {n} preceding))" + )), + "PRS-124", + "a split token is not one integer literal" + ); + } + assert_eq!( + code("(sum ?v :over (:order-by ?v :rows 9223372036854775808 preceding))"), + "INT-008", + "integer overflow is rejected by the lexer" + ); + } + + #[test] + fn final_order_by_distinguishes_window_frames() { + let query = |order: &str| { + format!( + "(query [:find ?v (sum ?v :over (:order-by ?v :rows 1 preceding)) \ + :where [?e :v ?v] :order-by [{order}]])" + ) + }; + parse_datalog_command(&query("(sum ?v :over (:order-by ?v :rows 1 preceding))")) + .expect("matching frame"); + let error = parse_datalog_command(&query("(sum ?v :over (:order-by ?v))")) + .err() + .expect("different frame"); + assert_eq!(crate::MinigrafError::from(error).code(), "PRS-117"); + } + #[test] fn parse_window_rank_desc() { let cmd = parse_datalog_command( diff --git a/src/query/datalog/parser/verifier.rs b/src/query/datalog/parser/verifier.rs index f83c1b9c9d..90be92045f 100644 --- a/src/query/datalog/parser/verifier.rs +++ b/src/query/datalog/parser/verifier.rs @@ -66,7 +66,7 @@ fn alphabet() -> Vec { a } -const TOKENS: [&str; 38] = [ +const TOKENS: [&str; 40] = [ "(", ")", "[", @@ -93,6 +93,8 @@ const TOKENS: [&str; 38] = [ ":distinct", ":asc", ":desc", + ":rows", + "preceding", ":valid-from", ":foo", "?x", @@ -114,7 +116,7 @@ fn bracket(t: u8) -> Option<(u8, bool)> { /// `(prefix, suffix)`: the hole sits between them. Each puts the hole where a short /// filler can complete a clause. -const TEMPLATES: [(&str, &str); 16] = [ +const TEMPLATES: [(&str, &str); 17] = [ ("(query [", "])"), ("(query [:find", ":where [?x :a ?y]])"), ("(query [:find ?x :where [?x :a ?y]", "])"), @@ -124,6 +126,10 @@ const TEMPLATES: [(&str, &str); 16] = [ ("(query [:find ?x :where [?x :a ?y] (or-join [?x]", ")])"), ("(query [:find ?x :where [?x :a ?y] (or (and", "))])"), ("(query [:find ?x (sum ?y :over (", ")) :where [?x :a ?y]])"), + ( + "(query [:find ?x (sum ?y :over (:order-by ?y ", + ")) :where [?x :a ?y]])", + ), ("(query [:find ?x :where [?x :a ?y] :order-by [", "]])"), ("(transact [", "])"), ("(transact [[:a :b 1", "]])"), @@ -212,6 +218,12 @@ const SEMANTIC: &[Semantic] = &[ code: "PRS-084", witness: "(query [:find ?x (sum ?y :over ()) :where [?x :a ?y]])", }, + // parse_window: the syntax is valid, but a position function has no + // aggregate frame to bound. + Semantic { + code: "PRS-125", + witness: "(query [:find (rank :over (:order-by ?y :rows 1 preceding)) :where [?x :a ?y]])", + }, // parse_query: a query option given twice (`query_section+` allows any repeat); // `:limit 1 :limit 1` is a 4-token filler (#306). Semantic { @@ -532,10 +544,10 @@ fn filler_counts_match_the_spec() { } n }; - // 38 tokens: the #643 spec's 32, `#{` (#316), `:limit`, `:offset`, - // `:asc`, `:desc` (#306), and `:distinct` (#493). - assert_eq!(count(3), 34_116); - assert_eq!(count(4), 1_101_142); + // 40 tokens: the #643 spec's 32, `#{` (#316), `:limit`, `:offset`, + // `:asc`, `:desc` (#306), `:distinct` (#493), and `:rows`, `preceding` (#183). + assert_eq!(count(3), 40_804); + assert_eq!(count(4), 1_397_966); } #[test] diff --git a/src/query/datalog/types.rs b/src/query/datalog/types.rs index 19aa33b30e..87d5a972bd 100644 --- a/src/query/datalog/types.rs +++ b/src/query/datalog/types.rs @@ -131,6 +131,12 @@ pub enum Order { Desc, } +/// An explicit frame for an aggregate window. +#[derive(Debug, Clone, PartialEq)] +pub enum WindowFrame { + RowsPreceding(u64), +} + /// The `:over (...)` clause of a window function expression. #[derive(Debug, Clone, PartialEq)] pub struct WindowSpec { @@ -142,6 +148,8 @@ pub struct WindowSpec { /// Sort key variable (required — parser enforces this). pub order_by: String, pub order: Order, + /// None keeps the default peer-based cumulative frame. + pub frame: Option, } impl WindowSpec { @@ -1143,6 +1151,7 @@ mod tests { partition_by: None, order_by: "?x".to_string(), order: Order::Asc, + frame: None, } .func_name(), "sum" @@ -1154,6 +1163,7 @@ mod tests { partition_by: None, order_by: "?x".to_string(), order: Order::Desc, + frame: None, } .func_name(), "rank" @@ -1165,6 +1175,7 @@ mod tests { partition_by: None, order_by: "?x".to_string(), order: Order::Asc, + frame: None, } .func_name(), "row-number" @@ -1175,6 +1186,7 @@ mod tests { partition_by: None, order_by: "?o".to_string(), order: Order::Asc, + frame: None, }; assert_eq!(ws_udf.func_name(), "geomean".to_string()); } @@ -1187,6 +1199,7 @@ mod tests { partition_by: None, order_by: "?date".to_string(), order: Order::Asc, + frame: None, }; let spec = FindSpec::Window(ws_with_var); assert_eq!(spec.display_name(), "(sum ?salary :over ...)"); @@ -1197,6 +1210,7 @@ mod tests { partition_by: None, order_by: "?date".to_string(), order: Order::Desc, + frame: None, }; let spec2 = FindSpec::Window(ws_no_var); assert_eq!(spec2.display_name(), "(rank :over ...)"); diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 7ec8559ba2..7785b64b79 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -2632,25 +2632,22 @@ fn window_result_columns_count_toward_query_memory_limit() { .path(&path) .open() .unwrap(); - let mut cursor = db - .query( - "(query [:find ?e (min ?v :over (:order-by ?v)) \ - (max ?v :over (:order-by ?v)) :where [?e :text ?v]])", - ) - .unwrap(); - let meter = cursor.stream_mut().expect("engine").meter().clone(); - let err = match cursor.next_batch(1) { - Ok(_) => panic!("window result columns must count"), - Err(err) => err, - }; - assert_eq!(err.code(), "QRY-012"); - assert!(err.to_string().contains("Window needs")); - assert_eq!( - meter.used(), - 0, - "an error releases the held columns and input" - ); - drop(cursor); + for query in [ + "(query [:find ?e (min ?v :over (:order-by ?v)) \ + (max ?v :over (:order-by ?v)) :where [?e :text ?v]])", + "(query [:find ?e (min ?v :over (:order-by ?v :rows 1 preceding)) \ + (max ?v :over (:order-by ?v :rows 1 preceding)) :where [?e :text ?v]])", + ] { + let mut cursor = db.query(query).unwrap(); + let meter = cursor.stream_mut().expect("engine").meter().clone(); + let err = match cursor.next_batch(1) { + Ok(_) => panic!("window result columns must count"), + Err(err) => err, + }; + assert_eq!(err.code(), "QRY-012"); + assert!(err.to_string().contains("Window needs")); + assert_eq!(meter.used(), 0, "an error releases held window state"); + } drop(db); let db = crate::OpenOptions::new().path(&path).open().unwrap(); @@ -2710,6 +2707,7 @@ fn window_partition_indices_count_toward_query_memory_limit() { partition_by: Some("?p".into()), order_by: "?o".into(), order: Order::Asc, + frame: None, }); let find = vec![FindSpec::Variable("?p".into()), window.clone(), window]; let rows: Vec> = (0..N) @@ -2778,6 +2776,7 @@ fn window_partition_index_allocator_refusal_is_qry_012() { partition_by: None, order_by: "?o".into(), order: Order::Asc, + frame: None, })]; let rows = vec![vec![crate::Value::Integer(1)]; N]; let meter = super::Meter::unlimited(); @@ -2814,6 +2813,7 @@ fn window_partition_indices_release_on_running_error() { partition_by: None, order_by: "?v".into(), order: Order::Asc, + frame: None, })]; let rows = vec![vec![crate::Value::Integer(1)]; N]; let meter = super::Meter::unlimited(); @@ -2845,6 +2845,7 @@ fn empty_window_does_not_charge_partition_indices() { partition_by: None, order_by: "?v".into(), order: Order::Asc, + frame: None, })]; let meter = super::Meter::unlimited(); let mut held = Held::new(&meter, "Window"); @@ -2883,6 +2884,7 @@ fn window_partition_sort_preserves_positions_peers_and_neighbors() { partition_by: Some("?p".into()), order_by: "?o".into(), order: Order::Asc, + frame: None, })); } let rows: Vec> = (0..N) @@ -3241,6 +3243,124 @@ fn meter_peak_against_rss() { } } +/// Reproduce the engine meter's peak for the Criterion `window_rows` cases. +/// Run alone on the bench machine with `--ignored --nocapture`; the regular +/// suite does not build the 100,000-row fixture. +#[test] +#[ignore] +fn window_rows_benchmark_meter_peaks() { + for n in [10_000usize, 100_000] { + let db = Minigraf::in_memory().expect("memory database"); + for start in (0..n).step_by(100) { + let mut command = String::from("(transact ["); + for row in start..(start + 100).min(n) { + command.push_str(&format!("[:e{row} :val {row}]")); + } + command.push_str("])"); + db.execute(&command).expect("value facts"); + } + let partition_len = n / 100; + for start in (0..n).step_by(100) { + let mut command = String::from("(transact ["); + for row in start..(start + 100).min(n) { + command.push_str(&format!("[:e{row} :part {}]", row / partition_len)); + } + command.push_str("])"); + db.execute(&command).expect("partition facts"); + } + db.register_aggregate( + "frame_bench_sum", + || 0i64, + |sum, value| { + if let crate::Value::Integer(v) = value { + *sum += *v; + } + }, + |sum, _| crate::Value::Integer(*sum), + ) + .expect("aggregate registration"); + for (shape, partition_by, part_size) in [ + ("one", "", n), + ("hundred", ":partition-by ?p ", partition_len), + ] { + let widths = [ + ("default", None), + ("zero", Some(0)), + ("two", Some(2)), + ("sqrt", Some(part_size.isqrt())), + ("half", Some(part_size / 2)), + ("prefix", Some(part_size)), + ]; + for func in ["sum", "count", "min", "max", "avg", "frame_bench_sum"] { + for (width_name, width) in widths { + if func == "frame_bench_sum" + && ((n == 100_000 && width_name != "prefix") + || (n == 10_000 && !["zero", "two", "half"].contains(&width_name))) + { + continue; + } + let frame = width.map_or_else(String::new, |w| format!(":rows {w} preceding ")); + let query = format!( + "(query [:find ?e ({func} ?v :over ({partition_by}:order-by ?v {frame})) \ + :where [?e :val ?v] [?e :part ?p]])" + ); + let mut cursor = db.query(&query).expect("window query"); + let meter = cursor.stream_mut().expect("engine stream").meter().clone(); + let mut row_count = 0usize; + while let Some(batch) = cursor.next_batch(1024).expect("window batch") { + row_count += batch.len(); + } + assert_eq!(row_count, n); + cursor.close(); + eprintln!( + "window_rows/{n}/{shape}/{func}/{width_name},{}", + meter.peak() + ); + assert_eq!(meter.used(), 0, "meter released after cursor close"); + } + } + } + } +} + +#[test] +fn zero_width_min_frame_charges_one_deque_slot() { + use super::meter::Held; + use crate::query::datalog::aggregate::{WindowColumn, windows}; + use crate::query::datalog::functions::FunctionRegistry; + use crate::query::datalog::types::{FindSpec, Order, WindowFrame, WindowFunc, WindowSpec}; + use std::mem::size_of; + + const N: usize = 512; + let find = [ + FindSpec::Variable("?v".into()), + FindSpec::Window(WindowSpec { + func: WindowFunc::Min, + var: Some("?v".into()), + partition_by: None, + order_by: "?v".into(), + order: Order::Asc, + frame: Some(WindowFrame::RowsPreceding(0)), + }), + ]; + let rows: Vec> = (0..N) + .map(|n| vec![crate::Value::Integer(i64::try_from(n).expect("row"))]) + .collect(); + let limit = N * size_of::() + + size_of::() + + N * size_of::() + + size_of::(); + let meter = super::Meter::new(limit); + let mut held = Held::new(&meter, "Window"); + let columns = windows(&find, &rows, &FunctionRegistry::with_builtins(), &mut held) + .expect("zero-width min window fits the budget"); + assert_eq!(columns.len(), 1); + assert_eq!(meter.peak(), limit); + drop(columns); + held.release(); + assert_eq!(meter.used(), 0); +} + /// `Aggregate::finish` charges its sorted map of groups until every row is /// built, and lets the hash table and group rows go first, so once rows are /// returned only the ones not yet returned stay charged (#549). diff --git a/tests/error_codes_qry_test.rs b/tests/error_codes_qry_test.rs index 3022f78d73..b3b28ec7fa 100644 --- a/tests/error_codes_qry_test.rs +++ b/tests/error_codes_qry_test.rs @@ -124,6 +124,8 @@ fn assert_query_code(db: &Minigraf, query: &str, expected: &str) { const UNKNOWN_AGG: &str = r#"(query [:find (frob414 ?b) :where [?a :x ?b]])"#; const UNKNOWN_WINDOW: &str = r#"(query [:find ?b (frob414 ?b :over (:order-by ?b)) :where [?a :x ?b]])"#; +const UNKNOWN_FRAMED_WINDOW: &str = + r#"(query [:find ?b (frob414 ?b :over (:order-by ?b :rows 1 preceding)) :where [?a :x ?b]])"#; #[test] fn unknown_aggregate_on_empty_database_returns_qry_010() { @@ -159,21 +161,27 @@ fn unknown_aggregate_in_rule_query_returns_qry_010() { #[test] fn unknown_window_function_on_empty_database_returns_qry_011() { let db = Minigraf::in_memory().unwrap(); - assert_query_code(&db, UNKNOWN_WINDOW, "QRY-011"); + for query in [UNKNOWN_WINDOW, UNKNOWN_FRAMED_WINDOW] { + assert_query_code(&db, query, "QRY-011"); + } } #[test] fn unknown_window_function_with_no_matching_rows_returns_qry_011() { let db = Minigraf::in_memory().unwrap(); db.execute(r#"(transact [[:a :y 1]])"#).unwrap(); - assert_query_code(&db, UNKNOWN_WINDOW, "QRY-011"); + for query in [UNKNOWN_WINDOW, UNKNOWN_FRAMED_WINDOW] { + assert_query_code(&db, query, "QRY-011"); + } } #[test] fn unknown_window_function_with_matching_rows_returns_qry_011() { let db = Minigraf::in_memory().unwrap(); db.execute(r#"(transact [[:a :x 1]])"#).unwrap(); - assert_query_code(&db, UNKNOWN_WINDOW, "QRY-011"); + for query in [UNKNOWN_WINDOW, UNKNOWN_FRAMED_WINDOW] { + assert_query_code(&db, query, "QRY-011"); + } } #[test] @@ -198,7 +206,7 @@ fn registered_udf_aggregate_and_window_on_empty_database_return_empty() { |acc: &i64, _n: usize| minigraf::Value::Integer(*acc), ) .unwrap(); - for q in [UNKNOWN_AGG, UNKNOWN_WINDOW] { + for q in [UNKNOWN_AGG, UNKNOWN_WINDOW, UNKNOWN_FRAMED_WINDOW] { match db.execute(q).expect("registered UDF query must succeed") { minigraf::QueryResult::QueryResults { results, .. } => { assert!(results.is_empty(), "expected no rows") diff --git a/tests/grammar/grammar.pest b/tests/grammar/grammar.pest index 73db6ec2b7..e12e492ae2 100644 --- a/tests/grammar/grammar.pest +++ b/tests/grammar/grammar.pest @@ -23,6 +23,7 @@ kw_limit = @{ ":limit" ~ !word_cont } kw_offset = @{ ":offset" ~ !word_cont } kw_distinct = @{ ":distinct" ~ !word_cont } kw_over = @{ ":over" ~ !word_cont } +kw_rows = @{ ":rows" ~ !word_cont } kw_partition_by = @{ ":partition-by" ~ !word_cont } kw_order_by = @{ ":order-by" ~ !word_cont } kw_desc = @{ ":desc" ~ !word_cont } @@ -148,12 +149,15 @@ aggregate_expr = { "(" ~ (op_sym | plain_sym) ~ variable ~ ")" } window_expr = { "(" ~ (op_sym | plain_sym) ~ (variable ~ kw_over | kw_over) ~ over_clause ~ ")" } -over_clause = { "(" ~ over_option* ~ ")" } -over_option = { +// Keep at most one row frame while letting it appear anywhere among options. +over_clause = { "(" ~ over_plain_option* ~ (row_frame ~ over_plain_option*)? ~ ")" } +over_plain_option = { kw_partition_by ~ variable | kw_order_by ~ variable | kw_desc | kw_asc } +row_frame = { kw_rows ~ frame_width ~ ("preceding" ~ !word_cont) } +frame_width = @{ ("-" ~ "0"+ | ASCII_DIGIT+) ~ !("." ~ ASCII_DIGIT) } // ── WHERE SECTION ───────────────────────────────────────────────────────── where_section = { kw_where ~ where_clause+ } diff --git a/tests/grammar/invalid/semantic/query_window_rows_rank.edn b/tests/grammar/invalid/semantic/query_window_rows_rank.edn new file mode 100644 index 0000000000..dd2be15a2c --- /dev/null +++ b/tests/grammar/invalid/semantic/query_window_rows_rank.edn @@ -0,0 +1,2 @@ +(query [:find (rank :over (:order-by ?v :rows 1 preceding)) + :where [?e :v ?v]]) diff --git a/tests/grammar/invalid/syntax/query_window_rows_duplicate.edn b/tests/grammar/invalid/syntax/query_window_rows_duplicate.edn new file mode 100644 index 0000000000..3837e792e7 --- /dev/null +++ b/tests/grammar/invalid/syntax/query_window_rows_duplicate.edn @@ -0,0 +1,2 @@ +(query [:find ?v (sum ?v :over (:order-by ?v :rows 1 preceding :rows 2 preceding)) + :where [?e :v ?v]]) diff --git a/tests/grammar/invalid/syntax/query_window_rows_missing_suffix.edn b/tests/grammar/invalid/syntax/query_window_rows_missing_suffix.edn new file mode 100644 index 0000000000..7564b3e78b --- /dev/null +++ b/tests/grammar/invalid/syntax/query_window_rows_missing_suffix.edn @@ -0,0 +1,2 @@ +(query [:find ?v (sum ?v :over (:order-by ?v :rows 2)) + :where [?e :v ?v]]) diff --git a/tests/grammar/valid/query_window_rows_adjacent.edn b/tests/grammar/valid/query_window_rows_adjacent.edn new file mode 100644 index 0000000000..703f81c736 --- /dev/null +++ b/tests/grammar/valid/query_window_rows_adjacent.edn @@ -0,0 +1,2 @@ +(query [:find ?v (sum ?v :over (:order-by ?v :rows 2preceding)) + :where [?e :v ?v]]) diff --git a/tests/grammar/valid/query_window_rows_leading_zero.edn b/tests/grammar/valid/query_window_rows_leading_zero.edn new file mode 100644 index 0000000000..5ccbb1e129 --- /dev/null +++ b/tests/grammar/valid/query_window_rows_leading_zero.edn @@ -0,0 +1,2 @@ +(query [:find ?v (avg ?v :over (:rows 007 preceding :order-by ?v)) + :where [?e :v ?v]]) diff --git a/tests/grammar/valid/query_window_rows_zero.edn b/tests/grammar/valid/query_window_rows_zero.edn new file mode 100644 index 0000000000..f535b4c493 --- /dev/null +++ b/tests/grammar/valid/query_window_rows_zero.edn @@ -0,0 +1,2 @@ +(query [:find ?v (sum ?v :over (:order-by ?v :rows -00 preceding)) + :where [?e :v ?v]]) diff --git a/tests/window_functions_test.rs b/tests/window_functions_test.rs index e0430302fc..3bf7b8a4f8 100644 --- a/tests/window_functions_test.rs +++ b/tests/window_functions_test.rs @@ -121,6 +121,285 @@ fn cumulative_sum_over_whole_result() { assert_eq!(row_110k[1], Value::Integer(380000)); } +#[test] +fn bounded_rows_sum_uses_current_and_one_previous_row() { + let db = setup_employees(); + let rows = get_results( + db.execute( + r#"(query [:find ?salary (sum ?salary :over (:order-by ?salary :rows 1 preceding)) + :where [?e :employee/salary ?salary]])"#, + ) + .expect("bounded window query"), + ); + assert_eq!(rows.len(), 4); + for (salary, sum) in [ + (85000, 85000), + (90000, 175000), + (95000, 185000), + (110000, 205000), + ] { + let row = rows.iter().find(|r| r[0] == Value::Integer(salary)); + assert_eq!(row.map(|r| &r[1]), Some(&Value::Integer(sum))); + } +} + +#[test] +fn bounded_rows_split_ties_and_reset_at_partitions() { + let db = Minigraf::in_memory().expect("in-memory db"); + db.execute( + r#"(transact [[:a :part "p1"] [:a :name "A"] [:a :ord 10] [:a :amount 2] + [:b :part "p1"] [:b :name "B"] [:b :ord 10] [:b :amount 3] + [:c :part "p1"] [:c :name "C"] [:c :ord 10] [:c :amount 5] + [:d :part "p2"] [:d :name "D"] [:d :ord 10] [:d :amount 7]])"#, + ) + .expect("transact"); + let rows = get_results( + db.execute( + r#"(query [:find ?part ?name ?amount + (sum ?amount :over (:partition-by ?part :order-by ?ord :rows 1 preceding)) + (count ?amount :over (:partition-by ?part :order-by ?ord :rows 1 preceding)) + (min ?amount :over (:partition-by ?part :order-by ?ord :rows 1 preceding)) + (max ?amount :over (:partition-by ?part :order-by ?ord :rows 1 preceding)) + (avg ?amount :over (:partition-by ?part :order-by ?ord :rows 1 preceding)) + :where [?e :part ?part] [?e :name ?name] + [?e :ord ?ord] [?e :amount ?amount]])"#, + ) + .expect("bounded aggregate windows"), + ); + let at = |name: &str| { + rows.iter() + .find(|r| r[1] == Value::String(name.to_string())) + .expect("named row") + }; + assert_eq!( + &at("A")[3..], + &[ + Value::Integer(2), + Value::Integer(1), + Value::Integer(2), + Value::Integer(2), + Value::Float(2.0) + ] + ); + assert_eq!( + &at("B")[3..], + &[ + Value::Integer(5), + Value::Integer(2), + Value::Integer(2), + Value::Integer(3), + Value::Float(2.5) + ] + ); + assert_eq!( + &at("C")[3..], + &[ + Value::Integer(8), + Value::Integer(2), + Value::Integer(3), + Value::Integer(5), + Value::Float(4.0) + ] + ); + assert_eq!( + &at("D")[3..], + &[ + Value::Integer(7), + Value::Integer(1), + Value::Integer(7), + Value::Integer(7), + Value::Float(7.0) + ] + ); +} + +#[test] +fn bounded_rows_zero_and_huge_width_in_descending_order() { + let db = setup_employees(); + let rows = get_results( + db.execute( + r#"(query [:find ?salary + (sum ?salary :over (:rows 0 preceding :order-by ?salary :desc)) + (sum ?salary :over (:order-by ?salary :desc :rows 9223372036854775807 preceding)) + :where [?e :employee/salary ?salary]])"#, + ) + .expect("bounded windows"), + ); + let at = |salary| { + rows.iter() + .find(|r| r[0] == Value::Integer(salary)) + .expect("salary") + }; + for (salary, prefix) in [ + (110000, 110000), + (95000, 205000), + (90000, 295000), + (85000, 380000), + ] { + assert_eq!(at(salary)[1], Value::Integer(salary)); + assert_eq!(at(salary)[2], Value::Integer(prefix)); + } +} + +#[test] +fn bounded_rows_udf_prepared_cursor_and_pagination() { + use minigraf::BindValue; + let db = Minigraf::in_memory().expect("in-memory db"); + db.register_aggregate( + "frame-total", + || 0i64, + |sum, value| { + if let Value::Integer(n) = value { + *sum += n; + } + }, + |sum, _| Value::Integer(*sum), + ) + .expect("register UDF"); + db.execute( + r#"(transact [[:a :group "g"] [:a :ord 1] [:a :v 2] + [:b :group "g"] [:b :ord 2] [:b :v nil] + [:c :group "g"] [:c :ord 3] [:c :v 5] + [:d :group "g"] [:d :ord 4] [:d :v 7]])"#, + ) + .expect("facts"); + let q = r#"(query [:find ?ord + (frame-total ?v :over (:order-by ?ord :rows 1 preceding)) + :where [?e :group $group] [?e :ord ?ord] [?e :v ?v] + :order-by [?ord] :offset 1 :limit 2])"#; + let prepared = db.prepare(q).expect("prepare"); + let bind = [("group", BindValue::Val(Value::String("g".into())))]; + let expected = vec![ + vec![Value::Integer(2), Value::Integer(2)], + vec![Value::Integer(3), Value::Integer(5)], + ]; + assert_eq!( + get_results(prepared.execute(&bind).expect("execute")), + expected + ); + let mut cursor = prepared.query(&bind).expect("cursor"); + let mut pulled = Vec::new(); + while let Some(batch) = cursor.next_batch(1).expect("batch") { + pulled.extend(batch.rows().iter().cloned()); + } + assert_eq!(pulled, expected); +} + +#[test] +fn bounded_rows_run_after_grouping_and_before_distinct() { + let db = setup_employees(); + let grouped = get_results( + db.execute( + r#"(query [:find ?dept (count ?e) + (count ?dept :over (:order-by ?dept :rows 1 preceding)) + :with ?e + :where [?e :employee/dept ?dept]])"#, + ) + .expect("grouped framed query"), + ); + assert_eq!(grouped.len(), 2); + assert!(grouped.contains(&vec![ + Value::String("Engineering".into()), + Value::Integer(2), + Value::Integer(1) + ])); + assert!(grouped.contains(&vec![ + Value::String("Product".into()), + Value::Integer(2), + Value::Integer(2) + ])); + + let db = Minigraf::in_memory().expect("in-memory db"); + db.execute(r#"(transact [[:a :v 1] [:b :v 1] [:c :v 1]])"#) + .expect("facts"); + let rows = get_results( + db.execute( + r#"(query [:find ?v (count ?v :over (:order-by ?v :rows 1 preceding)) + :where [?e :v ?v] :distinct])"#, + ) + .expect("distinct framed query"), + ); + assert_eq!(rows.len(), 2); + assert!(rows.contains(&vec![Value::Integer(1), Value::Integer(1)])); + assert!(rows.contains(&vec![Value::Integer(1), Value::Integer(2)])); +} + +#[cfg(feature = "test-hooks")] +#[test] +fn bounded_rows_answer_bag_is_plan_independent() { + use minigraf::{FactRecord, LogWriter, OpenOptions}; + use uuid::Uuid; + + let dir = tempfile::tempdir().expect("temp directory"); + let path = dir.path().join("row-frame-plan.graph"); + let mut writer = LogWriter::create(&path, OpenOptions::new()).expect("fact writer"); + let amounts = [ + Value::Integer(1), + Value::Float(1.0), + Value::Float(-0.0), + Value::Float(0.0), + Value::Float(f64::NAN), + Value::Integer(1), + ]; + for (pos, amount) in amounts.into_iter().enumerate() { + let entity = Uuid::from_u128(pos as u128 + 1); + for (attribute, value) in [ + (":name", Value::String("T".into())), + (":score", Value::Integer(1)), + (":amount", amount), + ] { + writer + .append(&FactRecord { + entity, + attribute: attribute.into(), + value, + tx_id: 1, + tx_count: 1, + valid_from: 0, + valid_to: i64::MAX, + asserted: true, + }) + .expect("fact"); + } + } + writer.finish().expect("finish facts"); + let db = Minigraf::open(&path).expect("open fixture"); + let q = r#"(query [:find ?name ?amount + (sum ?amount :over (:order-by ?score :rows 1 preceding)) + :where [?e :score ?score] [?e :name ?name] [?e :amount ?amount]])"#; + let run = |reorder| { + let _guard = minigraf::__reorder(reorder); + let mut rows = get_results(db.execute(q).expect("query")); + rows.sort(); + rows + }; + let without_reorder = run(false); + assert_eq!( + without_reorder.len(), + 6, + "every row stays in the answer bag" + ); + assert_eq!( + without_reorder + .iter() + .filter(|row| matches!(&row[1], Value::Float(f) if f.is_nan())) + .count(), + 1, + "NaN row participates in the window" + ); + let with_reorder = run(true); + assert_eq!(without_reorder.len(), with_reorder.len()); + for (left, right) in without_reorder.iter().zip(&with_reorder) { + assert_eq!(left.len(), right.len()); + for (a, b) in left.iter().zip(right) { + match (a, b) { + (Value::Float(a), Value::Float(b)) => assert_eq!(a.to_bits(), b.to_bits()), + (a, b) => assert_eq!(a, b), + } + } + } +} + // ── partition-by ──────────────────────────────────────────────────────────── #[test] From 6a7477c150d0340573e96534c481b2fef58b163e Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 27 Oct 2026 13:35:00 +0530 Subject: [PATCH 2/2] docs: target row frames in v3.0.0 (#183) --- CHANGELOG.md | 2 +- CLAUDE.md | 4 ++-- README.md | 2 +- ROADMAP.md | 2 +- docs/ERROR_REFERENCE.md | 4 ++-- docs/superpowers/plans/2026-10-27-183-row-frames.md | 2 +- docs/superpowers/specs/2026-10-27-183-row-frames-design.md | 2 +- 7 files changed, 9 insertions(+), 9 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 2bf3b3769f..74529c75d1 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -51,7 +51,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Added -- **Bounded sliding row frames** (#183; v3.next, unreleased). `:rows N preceding` adds a physical-row frame to window aggregates. Keep this change out of v3.0.0. +- **Bounded sliding row frames** (#183). `:rows N preceding` adds a physical-row frame to window aggregates. Built-in aggregates update the frame in linear time after sorting; registered aggregates replay bounded frames unless the frame covers the whole prefix. The default peer-based frame is unchanged. New parser codes `PRS-124` and `PRS-125` report malformed frames and frames on position functions. - **`lag` and `lead` window functions** (#182). `(lag ?value :over (:partition-by ?group :order-by ?key))` reads the previous row's value; `lead` reads the next row's. Both use the established total partition order, including named-variable tie breaks, and return `nil` at partition edges. `:desc` reverses the primary key, so the previous row has a higher or equal key. They run over grouped rows after aggregation and before `:distinct`, sorting and pagination. An optional offset or explicit default is not part of this release. The plain `(lag ?v)` and `(lead ?v)` forms remain available to registered user aggregates. `PRS-030` is deprecated and no longer emitted. - **Optional distinct query results** (#493). A bare `:distinct` flag removes repeated final `:find` tuples after aggregates and windows and before `:order-by`, `:offset` and `:limit`. Queries still return bags by default; `:with` keeps its aggregate grouping behavior. Equality follows `count-distinct` (including one NaN and one floating zero), with canonical `-0.0`/NaN output, also inside sets. The distinct keys count toward `query_memory_limit`; ordered top-k queries still retain a key for every unique tuple they encounter. - **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. diff --git a/CLAUDE.md b/CLAUDE.md index 4b5d7a5bf6..66df5fb239 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -227,8 +227,8 @@ See `docs/TEST_COVERAGE.md` for the full per-file breakdown. Current plan (see `ROADMAP.md` and the milestones): - **v2.x** (`main`, format v7) now gets only data-integrity and security fixes as patch releases (v2.0.3 is the first); v2.0.2 was the last planned v2.x release. -- **v3.0.0** (format v8 and data integrity, plus `:limit` #306, optional `:distinct` output #493, `lag`/`lead` #182, query profiler #185, set membership predicates #316 and prepared queries in every binding #181, UDF registration in every binding #180; tracker #383) is developed on the long-lived `v3` branch. All v3 PRs target `v3`; `main` stays untouched. CI runs on PRs to `v3` the same as on PRs to `main`. Do not merge `main` into `v3` routinely: `main` only gets backports of fixes already on `v3`. Shared CI and workflow changes land on both branches as separate PRs. Just before the v3.0.0 cut, merge `main` into `v3` once (merge commit; source conflicts resolved to `v3`, `main`'s v2.0.x CHANGELOG sections brought over) so the cut is a fast-forward. At the first v3 release, the current `main` is copied to `v2` and `v3` becomes the new `main`. -- **v3.next** (the release after v3.0.0) holds new features (sliding row frames #183, implemented but unreleased; rule persistence #241; OPFS `BrowserDb` #441). +- **v3.0.0** (format v8 and data integrity, plus `:limit` #306, optional `:distinct` output #493, `lag`/`lead` #182, sliding row frames #183, query profiler #185, set membership predicates #316 and prepared queries in every binding #181, UDF registration in every binding #180; tracker #383) is developed on the long-lived `v3` branch. All v3 PRs target `v3`; `main` stays untouched. CI runs on PRs to `v3` the same as on PRs to `main`. Do not merge `main` into `v3` routinely: `main` only gets backports of fixes already on `v3`. Shared CI and workflow changes land on both branches as separate PRs. Just before the v3.0.0 cut, merge `main` into `v3` once (merge commit; source conflicts resolved to `v3`, `main`'s v2.0.x CHANGELOG sections brought over) so the cut is a fast-forward. At the first v3 release, the current `main` is copied to `v2` and `v3` becomes the new `main`. +- **v3.next** (the release after v3.0.0) holds new features (rule persistence #241; OPFS `BrowserDb` #441). - Known v2.x data issue: same-transaction multi-valued facts (#371). Fix ships in v3.0.0. All v2.x known issues are listed in pinned issue #421 (`known-issue` label); `data-integrity`/`corruption`/`durability` issues fixed in a v2.x patch stay open until that patch is published; issues fixed on the unreleased `v3` branch close on merge (closing keywords do not fire on `v3`, so close them with `gh issue close`) and stay listed in #421 (CONTRIBUTING.md). - Support policy and tiers: PHILOSOPHY.md §7 and §10. v2.x gets data-integrity and security fixes for 12 months after v3.0.0. Tier 1 = Rust + Python + browser WASM (from v3.0.0); other bindings are Tier 2. diff --git a/README.md b/README.md index b082d8df15..94c4ff1130 100644 --- a/README.md +++ b/README.md @@ -30,7 +30,7 @@ Minigraf is a **single-file embedded graph database** that lets you: For example, `(lag ?salary :over (:partition-by ?dept :order-by ?hire-date))` reads the preceding employee's salary within each department; the first row gets `nil`. `lead` reads the following row. -Unreleased #183 work adds bounded sliding windows such as `(avg ?salary :over (:partition-by ?dept :order-by ?hire-date :rows 2 preceding))`. The feature is planned for v3.next and is not in a published release. +The unreleased v3.0.0 branch adds bounded sliding windows such as `(avg ?salary :over (:partition-by ?dept :order-by ?hire-date :rows 2 preceding))` (#183). **Status**: See [ROADMAP.md](ROADMAP.md) for planned work and current direction. diff --git a/ROADMAP.md b/ROADMAP.md index 2bf098379a..fa18ba13f3 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -95,6 +95,7 @@ Scope — query API: - Optional `:distinct` result tuples, preserving bag output by default (#493; done on `v3`) - `lag` and `lead` window functions for the previous/next row within an ordered partition (#182; v3.0.0) +- Bounded sliding row frames, `:rows N preceding`, for window aggregates (#183; v3.0.0, implemented on `v3`; builds on #182) - 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`, `: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. @@ -129,7 +130,6 @@ Scope — release-gate testing and documentation: Additive features, kept out of v3.0.0 so the #371 fix is not held up by them: - Rule persistence — design first (#241) -- Sliding row frames — `:rows N preceding` (#183; implemented for v3.next, unreleased; hold the PR merge until after the v3.0.0 cut; builds on #182) - OPFS-backed persistent mode for `BrowserDb`: a sync access handle in a dedicated Worker, no in-memory buffer; IndexedDB stays the main-thread backend. Starts at Tier 2 inside the Tier 1 browser binding until it has shipped (#441) - Temporal graph-traversal research (#273; may result in documentation or a blog post rather than code) diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index aa12710c10..e87caf3d5c 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -941,10 +941,10 @@ See the [Datalog Reference](https://project-minigraf.github.io/minigraf-docs/lat **Error text**: `unknown option in ':over' clause: '{}'` -**Cause**: An unrecognised keyword appeared inside the `:over` list. Valid options are `:order-by`, `:partition-by`, `:asc`, `:desc`, and (from v3.next) `:rows N preceding`. +**Cause**: An unrecognised keyword appeared inside the `:over` list. Valid options are `:order-by`, `:partition-by`, `:asc`, `:desc`, and (from v3.0.0) `:rows N preceding`. **Resolution**: -- Use `:order-by`, `:partition-by`, `:asc`, `:desc`, or `:rows N preceding` (from v3.next). +- Use `:order-by`, `:partition-by`, `:asc`, `:desc`, or `:rows N preceding` (from v3.0.0). - See the [Datalog Reference — Window Functions](https://project-minigraf.github.io/minigraf-docs/latest/datalog-reference/#window-functions). **Example**: diff --git a/docs/superpowers/plans/2026-10-27-183-row-frames.md b/docs/superpowers/plans/2026-10-27-183-row-frames.md index baa7efd209..a159e9687c 100644 --- a/docs/superpowers/plans/2026-10-27-183-row-frames.md +++ b/docs/superpowers/plans/2026-10-27-183-row-frames.md @@ -15,4 +15,4 @@ Implementation was rebased onto `origin/v3` at `f549245f4` after #765's window s 7. Commit a reproducible benchmark harness using the existing Criterion dev-dependency for framed sum/count/min/max/avg plus one UDF. On an otherwise idle bench machine, pin timing runs with `numactl` to one NUMA node and keep builds/tests out of the timing interval. For built-ins, use one partition and many equal-sized partitions, with total R=10,000 and 100,000 rows. Set N=0, 2, about √P, P/2, and at least P, where P is the partition length in each case. Warm each case and record at least five measured runs with median, range, and peak engine-meter bytes (the ignored `window_rows_benchmark_meter_peaks` diagnostic reproduces the datasets); record peak RSS where available. Compare built-ins to the same dataset's default frame. The built-in gate is median ≤5× the default at R=100,000 for each N, with no more than 15× growth from R=10,000 at comparable partition shape. If a gate fails, revise the algorithm and spec, obtain another Claude design review, and rerun the gate. For UDFs, measure R=10,000 with N=0, 2, and P/2, plus R=100,000 with N≥P to exercise the linear prefix path; report absolute times and callback counts. Do not run the quadratic R=100,000/P/2 UDF case. UDF middle-sized frames retain documented replay complexity. Discard timings from a busy machine. 8. After every remote test/benchmark run, remove only the scratch worktree, temporary target/fixture/run directories, and scripts that run created. Report what was kept and why. Reuse existing build caches deliberately; do not leave new scratch files behind. 9. Update repo docs and the docs-site Datalog reference with version-scoped text. Cross-check ROADMAP.md, README.md, CLAUDE.md, CHANGELOG.md, and docs/TEST_COVERAGE.md; update each affected status or inventory without calling the unreleased feature published. Make the docs-site change a separate PR, version-scoped so it does not prematurely claim a released version. No version bump or tag in this feature PR. -10. Apply verification-before-completion, inspect the diff and all required outputs, request Claude's independent final code review before opening the core PR, and verify every finding before acting. Open the core PR against `v3` as a draft only after that review; hold its merge until after the v3.0.0 cut, so #183 ships in v3.next. Do not merge without the user's explicit direction. +10. Apply verification-before-completion, inspect the diff and all required outputs, request Claude's independent final code review before opening the core PR, and verify every finding before acting. Open the core PR against `v3` after that review. The maintainer subsequently approved #183 for v3.0.0 and explicitly authorized merging both the core and docs PRs after version-scoped documentation is updated. diff --git a/docs/superpowers/specs/2026-10-27-183-row-frames-design.md b/docs/superpowers/specs/2026-10-27-183-row-frames-design.md index 19cd67d140..6a3c0561ae 100644 --- a/docs/superpowers/specs/2026-10-27-183-row-frames-design.md +++ b/docs/superpowers/specs/2026-10-27-183-row-frames-design.md @@ -1,6 +1,6 @@ # #183 Bounded sliding row frames — design -Date: 2026-10-27. Target: v3.next, based on current `origin/v3` (after #182 and #765). The PR against `v3` stays draft and must not merge before the v3.0.0 cut. Status: approved by Claude and maintainer after three design reviews. +Date: 2026-10-27. Target: v3.0.0 on `v3`, based on `origin/v3` after #182 and #765. The maintainer moved the release target from v3.next to v3.0.0 before merge. The design and code received Claude approval. ## Goal and philosophy