ADR 0014: Result order, limit, and the streaming merge contract¶

Status¶

Accepted. The ordered-limit collector contract is implemented. Search is cursorless: the agcur1 offset cursor shipped in agentgrep 0.1.0a22 is no longer accepted, and the keyset cursor proposed by the original OL-5 text was withdrawn before publication. This ADR allocates no replacement encoding.

Context¶

agentgrep search --limit N describes itself as “Limit the number of results after ranking”. It is not that. The driver stops collecting once the cap is reached while it walks sources in source-mtime order, and the newest-first sort is a post-hoc pass over whatever survived the cutoff. Two Codex sessions whose file mtime and record recency disagree are enough to expose it: with --limit 1 the record from the newer-mtime source is returned even though the older-mtime source holds the newest prompt. The genuinely newest record is discarded before the ranker ever compares it.

That is not a sorting bug. It is a layering error — ordering was treated as a frontend post-pass over a set the engine had already truncated. A limit is only meaningful relative to a declared order, so the two cannot live in different layers.

Three further facts frame the fix.

• The engine has no notion of order. search ranks by relevance in the frontend after collection, grep and the TUI want recency, and the collector itself yields in scan order. Nothing in the request names the desired list, so nothing in the result can name the list the caller got.

• The former MCP pagination path, released in agentgrep 0.1.0a22, used an agcur1 offset over a re-run scan: each page re-executed search with an inflated limit and sliced the sorted buffer. It inherited the defect above and paid a full rescan per page. This ADR removes that published continuation rather than retaining it.

• The concurrency question is already answered by the shipped code rather than by taste. ExecutionDriverConfig.max_workers defaults to 1, and nothing outside the tests raises it, so collection runs single-threaded today.

#100 surveyed twelve search and observability engines — Lucene, OpenSearch, tantivy, Meilisearch, fzf, Chroma, DataFusion, ClickHouse, Prometheus, Loki, Tempo, Pyroscope — and found one recipe under all of them: concurrent per-source fan-out that returns locally sorted, bounded output; a stable total-order key whose tiebreak is intrinsic and never arrival time; a completeness barrier before the global minimum is released; and a bounded top-k that lets a source stop early. This ADR adopts that recipe and settles the two decisions #100 deliberately left open — the ordering axis of the stream, and what defines the live watermark.

It also closes the tradeoff ADR 0004 left standing: “deterministic ordering and dedupe need explicit merge rules once execution becomes concurrent.”

Decision¶

Six invariants govern result order and bounding (OL for order and limit), in the enumerated style of ADR 0011.

• OL-1 — Order and limit are one indivisible core stage. No layer may apply a count cutoff in an order other than the order the caller declared. Every stop rule — bounded source scan, frontier skip, source cap, page fill — must be justifiable as “no record we have not examined can outrank the k-th record we already hold, under the declared order”. A stop rule that cannot state that invariant does not run. Where recency is inferred from file mtime rather than record timestamps, the invariant holds only under that approximation, and the run reports approximate (ADR 0004’s run-status vocabulary).

• OL-2 — order is a request parameter, executed in the collector, and echoed on the result. The vocabulary is fixed below. limit becomes a bounded top-k under the declared order — a k-sized frontier the collector maintains while it merges sources — not a cutoff on collection. The applied order travels back on the result payload and on the streaming summary, because a caller that cannot name the order it received cannot page it, diff it, or cache it. A frontend may still present records differently (grouping, highlighting, truncation), but it may not reorder or re-truncate the set.

• OL-3 — asyncio is a boundary protocol, never the engine’s concurrency model. The engine’s inner loop is CPU-bound under the GIL: json.loads → field extraction → casefold → substring test. An event loop cannot make that work finish sooner; it can only interleave it. asyncio’s job at the edges is real and stays: aiter_search_events already offloads the synchronous engine with asyncio.to_thread and pumps events through a bounded asyncio.Queue, which is what keeps the MCP server and the Textual pump responsive (ADR 0011). That is a protocol for delivering results without blocking a loop, not a strategy for computing them faster. The merge itself stays single-owner and synchronous, so the emitted order is a function of the records, never of arrival time.

• OL-4 — Parallelism comes from OS threads, and its ceiling is the interpreter build. Source scans fan out over concurrent.futures threads; the collector merges their locally sorted output on the owner thread. Under the default build the GIL caps the win, and measurement bears that out — a thread pool over local JSONL stores has measured slower than inline collection, which is why the shipped worker count is 1 and why ADR 0004 already records batch queueing as a loss. The lever is therefore the interpreter, not the architecture: the same thread fan-out that wins nothing under the GIL scales on a free-threaded build (PEP 703, supported since CPython 3.14 per PEP 779) with no code change. Design for threads; let the build decide the throughput.

• OL-5 — Search result windows are cursorless. limit caps one ordered response. Exact lookahead reports bounded with reason="result_limit" when another match exists, but it creates no continuation handle. MCP callers migrating from the released agcur1 search cursor rerun without cursor, then refine the query or raise limit. A future cursor requires its own snapshot, ordering, request-binding, and lifetime decision; this ADR fixes no token prefix, key shape, or replay contract. Find pagination is a separate discovery contract and retains its agcur1 cursor.

• OL-6 — The tier interface is decided now; the tier policy is deferred. The collector merges sorted source streams; whether a stream is a live file scan or an index cursor is invisible to it. That interface — one merge, N sorted inputs, one total-order key, one barrier — is settled by this ADR. What defines the live watermark (file mtime past the index build, an ingest opstamp, an explicit coverage flag) is not settled, and must not be, until an index exists to have a watermark. With no index every source is live, the barrier is trivially satisfied, and the design degrades cleanly to today’s behavior.

Prior art¶

Two upstream systems answer OL-3 and OL-4 directly, and both were read at the pinned ref below.

ripgrep (tag 15.1.0) is the closest analogue: a local, CPU-bound, filesystem-wide search. It runs its parallel search on OS threads — build_parallel over the directory walk — with no async runtime anywhere. More to the point for OL-1: when the user asks for a sorted output, ripgrep disables parallelism outright rather than merging out-of-order results afterward. Ordering is a property of the execution stage, not a post-pass bolted onto it.

aiosqlite (tag v0.22.1) is the canonical shape of OL-3: its Connection is a worker Thread fed by a SimpleQueue, and each coroutine awaits a future the thread resolves. The async surface is a delivery protocol over a threaded core — which is exactly what aiter_search_events already is, and exactly what it should remain.

Relationship to other ADRs¶

ADR 0004 owns planning, execution, the event stream, and the run-status/result vocabulary. This ADR resolves the merge-rules tradeoff it left open and adds order to the request and the result; the layering, the driver protocol, and the sink boundary are unchanged. ADR 0011 is untouched: OL-3 keeps the pump-facing async bridge exactly where it is. ADR 0006 governs how order and the echoed applied order surface on the CLI and MCP payloads. ADR 0003 is not invoked: nothing here approves native code, and OL-4’s throughput lever is an interpreter build, not a Rust engine. ADR 0020 owns how effort and scope select the sources entering this merge, while ADR 0021 owns the fixed targeted source selection.

Consequences¶

The engine gains a declared order it can be held to, and --limit starts meaning what its help text has always claimed. Ordering, dedupe, and bounding become one testable stage with one total-order key, so an inline driver and a threaded driver can be asserted to produce byte-identical lists. Removing the published offset continuation avoids repeated rescans without promising an unsupported replay contract. And the throughput story becomes a build choice rather than an async rewrite.

The costs are real. order is a new public request parameter, so CLI, MCP, and library surfaces each grow a field and each owe it a test. A bounded top-k frontier is more state than a counter. Search requests lose pagination outright — a deliberate loss, since the alternative is a cursor that silently returns a different list each page. The tier barrier adds a wait that, with no index, never triggers; it must not be allowed to rot untested in the meantime.

The chief risk is a frontend quietly re-truncating an ordered list — the very mistake this ADR exists to correct. The mitigation is OL-2’s echoed order plus the required focused regression, which must fail loudly when the engine’s order and limit disagree.

Final position¶

A limit without a declared order is a lie, and agentgrep has been telling it. Order and limit are one stage in the collector; asyncio delivers results without blocking a loop and computes nothing; threads carry the parallelism and the interpreter build sets its ceiling; search has no continuation; and the live-versus-indexed split is one more sorted input into the same merge, whose policy waits for an index worth having.