adityamukho · Oct 25, 2026 · Oct 24, 2026 · Oct 24, 2026 · Oct 24, 2026 · Oct 24, 2026
@@ -14,7 +14,7 @@ jobs:
     name: Check release binary size
     runs-on: ubuntu-latest
     env:
-      SIZE_LIMIT_BYTES: 1228800  # 1200 KiB — raised from 1 MiB for #277's structured error codes; see PHILOSOPHY.md §4
+      SIZE_LIMIT_BYTES: 1259520  # 1230 KiB — raised from 1 MiB for #277's structured error codes, from 1200 KiB for #306's :order-by/top-k; see PHILOSOPHY.md §4
     steps:
       - name: Checkout code
         uses: actions/checkout@v4

@@ -52,7 +52,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 ### Added
 
 - **Fallible and re-entrant user functions** (#180, PR 1). `Minigraf::try_register_predicate` and `Minigraf::try_register_aggregate` take closures that return `Result<_, UdfError>` (`UdfError` is exported at the crate root). A call that returns `Err` fails the query with the new `QRY-014`, ``user function `<name>` failed: <message>``, at the first failing call: it is never read as `false` or `nil`, and no later call of any user function is made for that query. `execute` and `PreparedQuery::execute` return it; a cursor treats it as any other read error, returning the rows of the batches finished before the failure, then the error, then `None`. `register_predicate` and `register_aggregate` are unchanged. A query now reads its functions from a snapshot of the registry taken when it opens, and holds no database lock while a user function runs: a function registered later is not seen by a query or cursor that is already open, and a user function may call back into its own database (query, prepare, read the fact log, write, define rules, register functions, checkpoint, verify, rebuild indexes). Its writes are not seen by the query that called it. Inside a `WriteTransaction` those calls return `INT-001` on that thread, except registration, which runs. Before, a user function that registered a function deadlocked. This is the core of UDF registration in the language bindings, which follows binding by binding.
-- **`:limit N` bounds the rows a query returns** (#306, PR 1 of 2). `[:find … :where … :limit 10]` returns at most 10 rows of the answer, and the engine stops reading once it has them: over 10M facts `:limit 10` reads one internal batch. Without `:order-by` (PR 2) which rows is unspecified, and may differ between plans; they are always rows of the unlimited answer. `:limit 0` returns no rows. It applies after aggregates and windows, to rule queries and to cursors, and a prepared query takes `:limit $n`, bound with `BindValue::Val(Value::Integer(n))`. A value that is not an integer `>= 0` or a slot fails with the new `PRS-115`; a repeated `:limit` with `INT-012` and a missing value with `INT-013`, as for the other query options. `:max-results` and `:max-derived-facts` still limit only the facts rules derive.
+- **`:limit N` bounds the rows a query returns** (#306). `[:find … :where … :limit 10]` returns at most 10 rows of the answer, and the engine stops reading once it has them: over 10M facts `:limit 10` reads one internal batch. Without `:order-by` which rows is unspecified, and may differ between plans; they are always rows of the unlimited answer. `:limit 0` returns no rows. It applies after aggregates and windows, to rule queries and to cursors, and a prepared query takes `:limit $n`, bound with `BindValue::Val(Value::Integer(n))`. A value that is not an integer `>= 0` or a slot fails with the new `PRS-115`; a repeated `:limit` with `INT-012` and a missing value with `INT-013`, as for the other query options. `:max-results` and `:max-derived-facts` still limit only the facts rules derive.
+- **`:order-by` and `:offset`** (#306). `:order-by [(count ?e) :desc ?name]` orders the rows a query returns by `:find` elements (plain variables, or aggregates and windows written as in `:find`), each `:asc` (the default) or `:desc`; ties are broken by the other `:find` columns ascending, so every position of an ordered answer is decided and every plan returns the same list. Values compare as windows and `min`/`max` compare them: numbers by value (an integer before an equal float, `-0.0` before `0.0`, NaN after every number), then strings, booleans, refs, keywords, `nil` and sets. `:offset N` skips the first `N` rows of the ordered answer, before `:limit`, so `:offset 20 :limit 10` is the third page of ten. A new `Sort` operator reads its whole input; under a `:limit` it keeps only the best `offset + limit` rows, so `:order-by [?v :desc] :limit 10` over 10M facts holds ten rows, not ten million. It applies after aggregates and windows, to rule queries, cursors and prepared queries (`:offset $o`, bound like `:limit`), and counts toward `query_memory_limit`. New codes: `PRS-116` (`:offset` without `:order-by`: without an order, pages could overlap or miss rows), `PRS-117` (an entry that is not a `:find` element) and `PRS-118` (`:order-by` is not a non-empty vector, names an element twice, or has a misplaced or unknown keyword). `PRS-115` now also covers `:offset`. Inside a window's `:over`, `:order-by` is unchanged.
 - **Set values: `#{...}`** (#316, PR 1 of 3). A fact's value can be a finite set of scalars, `[:alice :user/scopes #{:scope/read :scope/write}]`, written in query text, returned as `Value::Set(ValueSet)`, transacted, retracted and queried by exact value (`[?e :user/scopes #{:scope/write :scope/read}]`), joined on and grouped by. Duplicates are removed and element order does not matter. Two elements are the same when `Value`'s order says so: `0.0` and `-0.0` are one element (`-0.0` is kept), every NaN is one element, a keyword never equals a ref and `1` never equals `1.0`. A set cannot hold a set (`ValueSet::new` fails with the new `API-021`; in query text, `PRS-119`); its elements are literals only (`PRS-120`), and an unclosed `#{` is `PRS-121`. In format v8 a set has value tag `0x08`, after refs; a set whose encoded elements take at most 64 bytes is stored in its index keys, a longer one once in a value page, as a long string is. On a file database a stored set may take up to 4,068 bytes, counting each keyword element as 6 bytes and each ref as 10 (`WAL-003`). The REPL prints sets as `#{...}` and `BrowserDb` returns them as JSON arrays, in `Value`'s order.
 - **Set-membership predicates** (#316, PR 2 of 3). `[(in? ?role #{:role/admin :role/owner})]` keeps rows whose value is in a set, and `not-in?`, `any-in?` (the two sets share an element), `all-in?` (every element of the first is in the second) and `none-in?` (they share none) complete the five. Each works as a filter or binds a Boolean, `[(any-in? ?scopes #{:scope/write}) ?can-write]`, and takes literal sets, set-valued attributes and bind slots (`BindValue::Val(Value::Set(..))`). Membership is set equality, as for set values: `0.0` is in `#{-0.0}`, NaN is in a set holding NaN, a keyword is not a ref. `in?` of an empty set is false and `not-in?` true; `all-in?` and `none-in?` of an empty first set are true and `any-in?` false. A set where a scalar is needed, or a scalar where a set is needed, is a type mismatch: the filter drops the row and the binding binds nothing, so `not-in?` with a non-set is never true. `contains?` stays string-only. The five names cannot be registered as functions.
 - **`collect-set`** (#316, PR 3 of 3). `[(collect-set ?e :user/scope) ?scopes]` binds, per row, the set of the values of `[?e :user/scope ?v]` under the query's `:as-of` and `:valid-at`, with retractions applied as for that pattern, and `#{}` when there are none (the row is kept). Combine it with the set predicates: `[(collect-set ?e :user/scope) ?s] [(in? :scope/admin ?s)]`. `?e` must be bound by an earlier clause (`INT-018`); a keyword names its entity, and a value that is no entity gives `#{}`. It works in `:where`, rule bodies, `not-join` bodies and `or` branches; when its output variable is already bound, it keeps the rows where the two sets are equal. It reads stored facts only, never a rule's derived facts. New codes: `PRS-122` (no output variable), `PRS-123` (an operand that is not a `?variable` then an attribute keyword, a bind slot included) and `QRY-015` (a value found is itself a set: bind a set-valued attribute with a pattern). The set it builds counts toward `query_memory_limit` (`QRY-012`). `collect-set` is read only as a whole clause (`PRS-067` inside another expression) and cannot be registered as a function.

@@ -113,7 +113,9 @@ SQLite's success comes from a clear philosophy: be a library, not a server. Be s
   #277's structured error codes — 130 documented codes across 6 categories
   cannot fit in 1MB even with opt-level="z", LTO, codegen-units=1, and
   strip=symbols all already applied; see CI's `binary-size.yml` for the
-  enforced limit)
+  enforced limit). v3.0.0 raises the enforced limit to 1,230 KiB for
+  `:order-by`/`:offset` and the top-k `Sort` (#306), whose ~11 KiB did not
+  fit the 2 KiB left after the streaming engine (#473) and set values (#316)
 - No runtime dependencies (no JVM, no Python, no Node.js)
 
 **Anti-pattern**: Requiring external services, libraries, or runtimes to function.

@@ -23,7 +23,7 @@ Minigraf is a **single-file embedded graph database** that lets you:
 - ✅ **Query relationships with Datalog** - Recursive rules, natural graph traversal
 - ✅ **Time travel through history** - Bi-temporal queries (transaction time + valid time)
 - ✅ **Window functions** - `sum/count/min/max/avg/rank/row-number :over (partition-by … :order-by …)` in `:find` clauses
-- ✅ **Bounded results** - `:limit N` returns at most N rows and stops the work once it has them
+- ✅ **Bounded and ordered results** - `:limit N` returns at most N rows and stops the work once it has them; `:order-by [?score :desc] :limit 10` keeps only the top ten as it reads, and `:offset` pages through an ordered answer
 - ✅ **Prepared statements** - Parse + plan once with `$slot` bind tokens, execute thousands of times
 - ✅ **Embed anywhere** - Native, WASM, mobile, IoT - one `.graph` file
 - ✅ **Zero configuration** - Just `Minigraf::open("data.graph")` and you're done

@@ -94,7 +94,7 @@ Scope — format and storage integrity:
 Scope — query API:
 
 - Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) runs every query and produces rows as they are pulled: patterns, expressions and pseudo-attributes (#544), joins and `:db/valid-at` (#545), `not` and `or` (#546), aggregates and windows (#547), rules (#548), and transaction reads (#550); the executor's query path is gone (#551; done on `v3`). Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549).
-- Native `:limit N` (done on `v3`, with the 10M-fact acceptance test moved from #473), then `:order-by` and `:offset` with a top-k `Sort` (#306; spec `docs/superpowers/specs/2026-10-24-limit-order-by-design.md`).
+- Native `:limit N`, `:order-by` and `:offset`, with a top-k `Sort` whose memory follows `N` (#306; done on `v3`, with the 10M-fact acceptance tests moved from #473; spec `docs/superpowers/specs/2026-10-24-limit-order-by-design.md`). Skipping the sort when an index already returns the rows in order is #641 (v3.next).
 - Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log pins its generation: checkpoints run but do not reuse its pages (#543; `API-013` deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462.
 - Read-only open: `OpenOptions::read_only` takes a shared lock, so several readers can hold a file at once, writes nothing to the file or its WAL (a WAL is applied in memory, a v7 file is read without migrating), and refuses writes with `API-014` (#429; Rust API done on `v3`). The bindings' `open_with_options` follows.
 - Raw log writer: `LogWriter` builds a new database from `FactRecord`s with their `tx_count`, `tx_id`, valid-time windows and assertion flags kept, gaps allowed (a purged transaction stays a hole for `:as-of`), at `<path>.partial` renamed into place by `finish` (#431; Rust API done on `v3`). Completes extract (#429, #430), transform, load. The binding objects follow.

@@ -194,6 +194,8 @@ Measuring this found that `Aggregate` built its sorted map of groups uncharged w
 
 `limit` is `attribute_scan` with `:limit 10`: `Limit` closes the scan after its first internal batch, so the time does not grow with the facts (p50 307 µs, 317 µs and 318 µs at 100K, 1M and 10M, 5 MiB peak RSS each; `attribute_scan` reads the whole attribute in 43 ms, 462 ms and 4.83 s). Same idle server, one NUMA node, 2026-10-24. The acceptance test (`cargo test --profile bench --test limit_acceptance_test -- --ignored --nocapture`, nightly) runs `:limit 10` over 10M facts of one attribute in 0.8 ms under a 64 KiB `query_memory_limit`, adding 132 KiB of RSS.
 
+`top_k` is `attribute_scan` with `:order-by [?a :desc] :limit 10`: `Sort` reads the whole attribute but holds ten rows, so its time follows the scan and its memory does not (p50 22.4 ms, 241 ms and 2.54 s at 100K, 1M and 10M against `attribute_scan`'s 23.1 ms, 250 ms and 2.63 s on the same run; 6–7 MiB peak RSS at every scale). Same server, one NUMA node, 2026-10-25. The acceptance test runs `:order-by [?v :desc] :limit 10` over the same 10M facts in 28.5 s (bench profile, opt-level `z`) under a 1 MiB `query_memory_limit`, adding no measurable RSS. Skipping the read when an index returns the rows in order is #641.
+
 ### Executor removal (#551)
 
 Since #551 every query runs on the engine and the executor's query path is gone. Before it, the queries the engine could not plan ran on the executor, which reads every fact of the patterns' attributes into memory; the envelope's case is `:as-of` with a time. `as_of_ts` is the `as_of` point query with `:as-of "<time of transaction tx_half>"`; `as_of_ts_scan` is `[:find ?e ?a :as-of "<…>" :where [?e :age ?a]]` (8,400, 83,400 and 833,400 rows; 83,600 on the irregular copy). The fixture's `tx_id`s rise with `tx_count`, so the time becomes a counter bound. `1m-irregular` is a copy of the 1M fixture written with `LogWriter`, with each transaction's `tx_id` taken from a fixed permutation of the source's, so they fall and rise; there the engine filters on `tx_count` ranges instead.

@@ -136,6 +136,9 @@ with no `CodedError` anywhere in its chain.
 | PRS-113 | Unknown query keyword | Parser |
 | PRS-114 | Rule head argument is not a variable | Parser |
 | PRS-115 | Query option is not a non-negative integer | Parser |
+| PRS-116 | `:offset` without `:order-by` | Parser |
+| PRS-117 | `:order-by` entry is not a `:find` element | Parser |
+| PRS-118 | Malformed `:order-by` | Parser |
 | PRS-119 | Set literal inside a set literal | Parser |
 | PRS-120 | Set literal element is not a scalar literal | Parser |
 | PRS-121 | Unterminated set literal | Parser |
@@ -2151,10 +2154,10 @@ with `PRS-047`.
 
 **Error text**: `{} must be a non-negative integer or a bind slot, got {}`
 
-**Cause**: The value after `:limit` is not an integer `>= 0` or a `$slot`, or a prepared query's `:limit` slot was bound to a negative integer (#306).
+**Cause**: The value after `:limit` or `:offset` is not an integer `>= 0` or a `$slot`, or a prepared query's `:limit` or `:offset` slot was bound to a negative integer (#306).
 
 **Resolution**:
-- Give `:limit` a whole number of rows, `0` or more, or a bind slot filled with `BindValue::Val(Value::Integer(n))`.
+- Give `:limit` or `:offset` a whole number of rows, `0` or more, or a bind slot filled with `BindValue::Val(Value::Integer(n))`.
 
 **Example**:
 ```datalog
@@ -2164,6 +2167,59 @@ with `PRS-047`.
 
 ---
 
+### PRS-116 `:offset` without `:order-by`
+
+**Error text**: `:offset requires :order-by`
+
+**Cause**: The query has `:offset` but no `:order-by` (#306). Without an order, which rows an offset skips is unspecified: pages could overlap or miss rows between plans and between writes.
+
+**Resolution**:
+- Add `:order-by` naming the `:find` elements to page by.
+- To read a whole answer in pieces, use a cursor (`Minigraf::query`) instead of pages.
+
+**Example**:
+```datalog
+(query [:find ?e :where [?e :person/name ?n] :offset 20 :limit 10])
+```
+*No `:order-by`*
+
+---
+
+### PRS-117 `:order-by` entry is not a `:find` element
+
+**Error text**: `:order-by entry {} is not a :find element`
+
+**Cause**: An `:order-by` entry does not equal any `:find` element (#306). Entries name `:find` elements: plain variables, or aggregate and window elements written as they appear in `:find`. A variable bound in `:where` but not in `:find`, a `:with` variable, or a value that is neither a variable nor a list is rejected.
+
+**Resolution**:
+- Add the variable or aggregate to `:find`, or order by an element already there.
+- Write an aggregate entry exactly as in `:find`, e.g. `(count ?e)`.
+
+**Example**:
+```datalog
+(query [:find ?e :where [?e :person/age ?age] :order-by [?age]])
+```
+*`?age` is not in `:find`*
+
+---
+
+### PRS-118 Malformed `:order-by`
+
+**Error text**: `:order-by takes a non-empty vector of :find elements, each optionally followed by :asc or :desc; {}`
+
+**Cause**: The value after `:order-by` is not a vector, or is empty, or names the same element twice, or has `:asc`/`:desc` with no element before it (or two directions for one element), or holds another keyword (#306). The fault is named after the semicolon.
+
+**Resolution**:
+- Write `:order-by [?a :desc ?b]`: each `:find` element once, each optionally followed by one direction (default `:asc`).
+
+**Example**:
+```datalog
+(query [:find ?n :where [?e :person/name ?n] :order-by [:desc ?n]])
+```
+*`:desc` before its element*
+
+---
+
 ### PRS-119 Set literal inside a set literal
 
 **Error text**: `a set literal cannot hold a set`

@@ -20,6 +20,7 @@ kw-any-valid-time    ::= ":any-valid-time" (* not followed by word-cont *)  (* t
 kw-max-derived-facts ::= ":max-derived-facts" (* not followed by word-cont *)  (* token *)
 kw-max-results       ::= ":max-results" (* not followed by word-cont *)  (* token *)
 kw-limit             ::= ":limit" (* not followed by word-cont *)  (* token *)
+kw-offset            ::= ":offset" (* not followed by word-cont *)  (* token *)
 kw-over              ::= ":over" (* 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 *)
@@ -77,7 +78,8 @@ query-cmd     ::= "(" "query" query-vector ")"
 query-vector  ::= "[" query-section+ "]"
 query-section ::= find-section | where-section | as-of-section | valid-at-section
                 | any-valid-time-section | with-section | max-derived-facts-section
-                | max-results-section | limit-section
+                | max-results-section | limit-section | offset-section
+                | order-by-section
 
 (* ── FIND SECTION ── *)
 find-section   ::= kw-find find-spec+
@@ -124,6 +126,9 @@ with-section              ::= kw-with variable+
 max-derived-facts-section ::= kw-max-derived-facts integer-lit
 max-results-section       ::= kw-max-results integer-lit
 limit-section             ::= kw-limit (integer-lit | bind-slot)
+offset-section            ::= kw-offset (integer-lit | bind-slot)
+order-by-section          ::= kw-order-by "[" order-entry+ "]"
+order-entry               ::= find-spec (kw-asc | kw-desc)?
 
 (* ── RULE ── *)
 rule-cmd    ::= "(" "rule" rule-vector ")"