adityamukho · Oct 28, 2026 · Oct 28, 2026 · Oct 28, 2026
@@ -7,6 +7,12 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 
 ## [Unreleased]
 
+### Performance
+
+- **Skip sorting proven ordered input** (#641, first slice). Plain queries can omit `Sort` when a committed integer, float, or Boolean range already provides the complete ascending result order. Attribute scans use AVET; entity-and-attribute scans retain their selective EAVT range. `:offset` and `:limit` then stop reading early, so memory-limit (`QRY-012`) or I/O errors in unread later input may be avoided. The proof uses the query's pinned reader, including a large write transaction's working trees, and rejects pending or staged records in the source range, mixed kinds, unsupported comparators, tie suffixes, order-changing operators, user callbacks and `collect-set`. Unproven queries retain their original plan. Windows still buffer their full input pending the third slice.
+
+- **Release completed count groups** (#641, second slice). A plain query with exactly one proved scalar grouping key, no `:with` or windows, and only built-in `count`/`count-distinct` holds one active group plus bounded batches. Completed groups are released, and a limit can stop before later groups; one large distinct group still grows with its members. Integer, Boolean and committed-float keys qualify, including mixed integer/float grouping in `Value::Ord` order. A unique single-kind group key can also remove the final ascending Sort; mixed numeric keys retain numeric Sort. Fallible aggregates, callbacks and `collect-set` retain full-input validation and later errors. Small selective grouped queries pay proof startup cost, and a single growing group is slower (see `docs/BENCHMARKS.md`). No new aggregate syntax or function is added.
+
 ### Breaking changes
 
 - **`Value` is `#[non_exhaustive]` and has a `Set` variant** (#316). A `match` on `Value` outside the crate needs a wildcard arm, so later value kinds are not breaking changes.

@@ -32,6 +32,8 @@ For example, `(lag ?salary :over (:partition-by ?dept :order-by ?hire-date))` re
 
 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).
 
+On v3.0.0, an ascending value-only query such as `[:find ?v :where [?e :score ?v] :order-by [?v] :limit 10]` can read directly in index order and stop early when all committed `:score` history has one value kind (integer, float, or Boolean) and its source range has no pending writes. A query whose full order cannot be proved uses the existing sort (#641). Built-in `count` and `count-distinct` can also release completed groups when one committed integer/Boolean/float key is proved ordered (including mixed integer/float groups), with no `:with`, windows, callbacks or `collect-set`. Memory then follows the active group and batches; distinct members within one group still grow. Other aggregates keep full-input validation.
+
 **Status**: See [ROADMAP.md](ROADMAP.md) for planned work and current direction.
 
 ## Why Datalog?

@@ -98,7 +98,7 @@ Scope — query API:
 - 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).
 - Projected UUID lookup batches walk dense DICT ranges (#530; implemented on `v3`), keeping temporary memory bounded to a batch and query-cache charges in projection order.
-- 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).
+- 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`). #641 targets v3.0.0 in three slices: snapshot-bound order proofs and Sort omission for committed scalar ranges, then one-group count/count-distinct and partition-at-a-time windows. Sort omission and one-group count/count-distinct are implemented on `v3`; partition-at-a-time windows remain pending. Streaming groups require a proved scalar grouping key and no `:with`, windows, callbacks or `collect-set`; other aggregates retain full-input validation. See `docs/superpowers/specs/2026-10-28-641-input-order-design.md`.
 - Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log pins its generation: checkpoints run but do not reuse its pages (#543; `API-013` deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462.
 - Read-only open: `OpenOptions::read_only` takes a shared lock, so several readers can hold a file at once, writes nothing to the file or its WAL (a WAL is applied in memory, a v7 file is read without migrating), and refuses writes with `API-014` (#429; Rust API done on `v3`). The bindings' `open_with_options` follows.
 - Raw log writer: `LogWriter` builds a new database from `FactRecord`s with their `tx_count`, `tx_id`, valid-time windows and assertion flags kept, gaps allowed (a purged transaction stays a hole for `:as-of`), at `<path>.partial` renamed into place by `finish` (#431; Rust API done on `v3`). Completes extract (#429, #430), transform, load. The binding objects follow.

@@ -232,8 +232,98 @@ fn bench_query(c: &mut Criterion) {
     }
 }
 
+// Committed unique groups exercise both streaming count descriptors. The
+// ordinary ^query/ nightly route includes full drains and bounded limits.
+fn bench_ordered_groups(c: &mut Criterion) {
+    let mut group = c.benchmark_group("query/ordered_groups");
+    group.sample_size(10);
+    for (label, n) in [
+        ("1k", 1_000),
+        ("10k", 10_000),
+        ("100k", 100_000),
+        ("1m", 1_000_000),
+    ] {
+        for (mode, func, limited) in [
+            ("count", "count", false),
+            ("distinct", "count-distinct", false),
+            ("count_limit", "count", true),
+            ("distinct_limit", "count-distinct", true),
+        ] {
+            group.bench_with_input(BenchmarkId::new(mode, label), &n, |b, &n| {
+                let dir = tempfile::tempdir().unwrap();
+                let path = dir.path().join("groups.graph");
+                helpers::populate_file(n, path.to_str().unwrap());
+                let db = OpenOptions::new()
+                    .read_only(true)
+                    .path(&path)
+                    .open()
+                    .unwrap();
+                let query = format!(
+                    "(query [:find ?v ({func} ?e) :where [?e :val ?v] :order-by [?v] {}])",
+                    if limited { ":limit 10" } else { "" }
+                );
+                b.iter(|| {
+                    let mut cursor = db.query(&query).unwrap();
+                    let mut rows = 0;
+                    while let Some(batch) = cursor.next_batch(1000).unwrap() {
+                        rows += batch.len();
+                    }
+                    assert_eq!(rows, if limited { 10.min(n) } else { n });
+                    black_box(rows)
+                });
+            });
+        }
+    }
+    group.finish();
+}
+
 // ── Task 6: time_travel/ ──────────────────────────────────────────────────────
 
+// The existing nightly ^query/ filter selects both the proven value order and
+// its UUID-tie fallback control. All facts are committed, not in-memory pending.
+fn bench_input_order(c: &mut Criterion) {
+    let mut group = c.benchmark_group("query/ordered_values");
+    group.sample_size(10);
+    for (label, n) in [
+        ("1k", 1_000),
+        ("10k", 10_000),
+        ("100k", 100_000),
+        ("1m", 1_000_000),
+    ] {
+        for (mode, query) in [
+            (
+                "index",
+                "(query [:find ?v :where [?e :val ?v] :order-by [?v] :limit 10])",
+            ),
+            (
+                "uuid_ties",
+                "(query [:find ?e ?v :where [?e :val ?v] :order-by [?v] :limit 10])",
+            ),
+        ] {
+            group.bench_with_input(BenchmarkId::new(mode, label), &n, |b, &n| {
+                let dir = tempfile::tempdir().unwrap();
+                let path = dir.path().join("ordered.graph");
+                helpers::populate_file(n, path.to_str().unwrap());
+                let db = OpenOptions::new()
+                    .read_only(true)
+                    .path(&path)
+                    .open()
+                    .unwrap();
+                b.iter(|| {
+                    let minigraf::QueryResult::QueryResults { results, .. } =
+                        db.execute(query).unwrap()
+                    else {
+                        panic!("expected rows");
+                    };
+                    assert_eq!(results.len(), 10.min(n));
+                    black_box(results)
+                });
+            });
+        }
+    }
+    group.finish();
+}
+
 fn bench_time_travel(c: &mut Criterion) {
     const SCALES: &[(&str, usize)] = &[
         ("1k", 1_000),
@@ -1976,6 +2066,8 @@ criterion_group!(
     bench_insert,
     bench_insert_file,
     bench_query,
+    bench_input_order,
+    bench_ordered_groups,
     bench_time_travel,
     bench_recursion,
     bench_negation,