8000 feat(query): :order-by, :offset and top-k Sort (#306 PR 2) by adityamukho · Pull Request #755 · project-minigraf/minigraf · GitHub
[go: up one dir, main page]
Skip to content

feat(query): :order-by, :offset and top-k Sort (#306 PR 2) - #755

Merged
adityamukho merged 14 commits into
v3from
feat/306-order-by
Oct 25, 2026
Merged

feat(query): :order-by, :offset and top-k Sort (#306 PR 2)#755
adityamukho merged 14 commits into
v3from
feat/306-order-by

Conversation

@adityamukho
@adityamukho adityamukho commented Oct 25, 2026
Copy link
Copy Markdown
Collaborator

Part of #306 (PR 2 of 2: :order-by, :offset, top-k Sort). Spec docs/superpowers/specs/2026-10-24-limit-order-by-design.md; plan steps 10–17 detailed in docs/superpowers/plans/2026-10-24-306-limit-order-by.md (first commit).

What

  • Parser: :order-by [k :desc …] names :find elements (variables, aggregates, windows as written in :find, matched as FindSpec ==), :asc default; :offset N/$slot. New codes PRS-116 (:offset without :order-by), PRS-117 (entry not a :find element), PRS-118 (malformed :order-by); PRS-115 now covers :offset. INT-012/INT-013 as for the other options.
  • Prepared: :offset $o slots (resolve_count_slot).
  • Engine: Step::Sort { cols, order, keep } after Aggregate/Window, then Limit { offset, limit }. The full order is the keys, then every other :find column ascending, by value_order (aggregate::row_order). Sort holds the :find values, metered (QRY-012); under :limit it keeps a heap of the best offset + limit rows; :limit 0 pulls nothing. It drops the DICT lookups after each input batch, since kept they grow with the input (found by a test: top-k over committed data hit QRY-012 from IdSpace). Without keep, it heap-sorts with the same sift code instead of sort_unstable_by (saves ~5 KiB of binary).
  • Grammar: order_by_section, offset_section, corpus (4 valid, 3 syntax, 4 semantic); verifier 37 tokens, 16 templates, SEMANTIC witnesses for PRS-116–118. KNOWN_DRIFT empty at bound 3 (local) and bound 4 (bench).
  • Binary size gate 1,200 → 1,230 KiB (approved by the user): v3 was at 1,198 KiB in CI; this PR adds ~11 KiB (local 1,233 → 1,244). PHILOSOPHY.md §4 notes the raise.

Tests (bench machine)

  • Plain: 1,814 passed / 14 ignored (+18). test-hooks: 1,844 / 15 (+25).
  • tests/limit_order_test.rs: 14 ordered shapes (plain, join, not, or, grouped/ungrouped aggregates and the zero row, window, rule queries, :as-of, :any-valid-time, expression), in memory and on committed + pending facts, with every limit/offset combination, through execute, cursor, prepared and prepared cursor, reorder on/off: each equals the test's own full sort of the unlimited answer, sliced. Pages, every value class, write transactions, slot errors, QRY-012 for a full sort vs. top-k under the same limit. Two mutations (direction flipped, tie-break flipped) fail it.
  • Acceptance (limit_and_top_k_over_10m_facts, one fixture): :limit 10 0.72 ms, +132 KiB RSS; :order-by [?v :desc] :limit 10 returns the ten largest in 28.5 s (bench profile) under a 1 MiB limit, +0 KiB RSS.

Envelope (--profile envelope, one NUMA node), p50 / peak RSS

shape 100K 1M 10M
attribute_scan 23.1 ms / 6 MiB 250 ms / 7 MiB 2.63 s / 7 MiB
limit 316 µs / 5 MiB 322 µs / 5 MiB 326 µs / 5 MiB
top_k 22.4 ms / 6 MiB 241 ms / 7 MiB 2.54 s / 7 MiB

top_k costs a scan (skipping that is #641) and holds ten rows.

Docs: CHANGELOG, ERROR_REFERENCE, README, ROADMAP, CLAUDE.md, TEST_COVERAGE, BENCHMARKS. Docs site: project-minigraf/minigraf-docs PR (merge after this). Codex review: no findings.

🤖 Generated with Claude Code

https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF

adityamukho and others added 13 commits October 25, 2026 03:49
@adityamukho @claude
docs(plan): detail #306 PR 2 steps 10-17
c12c6a0 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho @claude
feat(parser): :order-by and :offset, PRS-116-118 (#306)
3cee008 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho @claude
feat(prepared): :offset bind slots (#306)
7836895 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho @claude
feat(aggregate): row_order, the full order of #306
f436d37 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho @claude
feat(engine): Sort with top-k, planned for :order-by/:offset (#306)
6a03d9a 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho @claude
fix(engine): Sort drops DICT lookups per input batch, so top-k memory…
db1ab36 
… follows k (#306)

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho @claude
test: ordered :order-by/:offset answers on every path (#306)
930beaf 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho @claude
test(grammar): :order-by and :offset sections, verifier tokens and wi…
9ec2940 
…tnesses (#306)

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
8000 @adityamukho @claude
test: top-k acceptance over 10M facts and envelope shape top_k (#306)
21ccfe1 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho @claude
docs: :order-by, :offset and Sort (#306)
eaeaa4f 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho @claude
perf(size): Sort sorts with its heap, not a second sort in the binary (…
e84e254 
…#306)

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho @claude
ci(size): 1,230 KiB gate for #306; docs: counts, top_k numbers
f6a5066 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho @claude
docs(plan): #306 PR 2 deviations
61229bb 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF
@adityamukho adityamukho mentioned this pull request Oct 25, 2026
Merged
@codecov
codecov Bot commented Oct 25, 2026
Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 96.86411% with 18 lines in your changes missing coverage. Please review.

Files with missing lines Patch % Lines
src/query/engine/sort.rs 97.16% 5 Missing and 4 partials ⚠️
src/query/datalog/parser.rs 98.17% 3 Missing ⚠️
src/query/engine/plan.rs 89.65% 2 Missing and 1 partial ⚠️
src/query/datalog/types.rs 50.00% 2 Missing ⚠️
src/query/engine/filter.rs 0.00% 1 Missing ⚠️

📢 Thoughts on this report? Let us know!

@adityamukho
adityamukho merged commit 09266d8 into v3 Oct 25, 2026
20 checks passed
@adityamukho
adityamukho deleted the feat/306-order-by branch October 25, 2026 04:29
@adityamukho adityamukho mentioned this pull request Oct 25, 2026
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

1 participant

@adityamukho
0