std/indexes:ordered — Range Guards Route Through the Store Index

std/indexes gained a second verb. std/indexes:ordered(<store>, <col>) declares an index on the same one-per-store slot std/indexes:store claims — either spelling, never both — but the structure behind it is a sorted directory instead of a key→bucket map, and that changes what a query guard can ask for.

What an ordered index routes

An equality index answers one question: which rows carry this key. An ordered index answers that and the questions around it — everything above a key, everything below, the first row past a bound. In Koru terms: ! query r when r.key >= k stops sweeping the store and walks a bounded window of the index instead.

import std/store
import std/indexes
import std/io

std/store:new(players, capacity: 8) { key: i64, val: i64 }
std/indexes:ordered(players, key)

std/store:insert(players) { key: 3, val: 30 }
std/store:insert(players) { key: 2, val: 20 }
std/store:insert(players) { key: 1, val: 10 }
std/store:insert(players) { key: 3, val: 31 }
std/store:insert(players) { key: 1, val: 11 }

std/store:query(players)
! query p when p.key >= 2 |> std/io:print.ln("ge2 {{ p.val:d }}")

The visit order is the index’s, not the store’s: the walk emits 20, 30, 31 — ascending key, join order inside each key’s bucket — even though dense order would say 30, 20, 31. The join order above is deliberately scrambled so a sweep can never satisfy the pinned output; route-vs-scan is observable in the result, not just the plan.

== doesn’t get a second structure for this — it routes through the same directory, as a binary search. The ordered declaration is a superset of the equality one, not a sibling mechanism.

What it lowers to

No new machinery family. Behind __index_<col> sits one sorted array of { key, members } entries: == is a binary search into it, a range is a bound plus a walk over the entries between, and both maintenance paths — insert and stored re-key — are the same binary-search probe. A stored write to the ordered column moves the row’s membership eagerly: out of the old key’s list, appended to the new one’s end, so the write cost is paid once and every reader sees it.

The semantics that matter are the same ones the equality index already carries, held at directory granularity: take inside a routed walk leaves a dead member every reader skips rather than renumbering the walk, a survival walk re-finds its entry by key because a mid-walk insert shifts positions, and ! first under a range answers the first member of the walk — the lowest matching key’s first member — not the lowest dense row. That last one is the visible contract: routed order is the order the language reports.

The seam it widened

Route-vs-scan was already the index architecture’s single decision point: guardRoute either proves the guard can be answered from the index or answers scan, and the sweep computes the same result the slow way. The ordered index is a widening of that one function — range arms were added at the boundary, not a feature beside it — which is why the declaration can share the equality slot instead of inventing a parallel mechanism.

Sharing the slot is also why one index per store is a refusal, not a silent pick: a second std/indexes:* declaration — any verb, any column — fails at compile time, naming the column already claimed. That wall exists because the discovery walk used to return the first declaration and never look again; the author believed the second column was indexed while every guard on it scanned. When multiple indexes arrive, the routing question is real — r.key >= 2 and r.val == 3 under two directories has to choose — but today the honest answer is that a store carries one directory and every routed guard goes through it.

The honest structure at store scale is the flat sorted directory plus binary search. A B-tree earns the slot only if a workload’s distinct-key domain ever outgrows it — the inspiration for looking at this seam at all was bbtree, whose actual contributions (inline keys, optimistic latch coupling, mmap layout) answer questions this seam doesn’t ask.

The open rungs

The experiment is deliberately bounded. The js and cs targets refuse an ordered declaration loudly rather than silently degrade to a sweep; the bulk insert path uses the straight-line per-row binary search rather than the equality map’s register-cached bucket trick; and ! first’s first-of-walk semantics under a range is the contract the pin chose — if a workload ever wants lowest-dense under a range, that’s a new question, not a bug in this one.